HDU1045-Fire-Net-暴力搜索DFS

JAY.LIN 收录于搜索专题 Hdu

2021-02-23 约 669 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=7698799

HDU1045 Fire Net 暴力搜索DFS

这题给出的图的行列范围较小，所以可以暴力来做。

要解决的问题就是怎样方便的枚举完所有可能的情况，并且得到放置blockhouse的最大值。

这要在dfs上下功夫了。

代码中的dfs原型为dfs(int i,int num)。其中 i 为记录该次搜索已经到达那一个点了(i=1、2、…、n*n ，

表示从左到右、从上到下给每个点编号）。num是用来记录当前搜索已经添加的blockhouse数目，另

一个功能就是当本次搜索结束，也就是i==n*n时，和全局变量maxNum比较并保留最大值放在maxNum

中。这样当所有情况都搜完后，maxNum要求值了。

还有一些小细节：

1、canPlace(int row,int col) 用来判断当前点 (row,col) 所在行列是否已经放置可以攻击到该点的blockhouse。

2、如果当前点可以放置blockhouse则标记为 ‘o’ 表示已放。当然也可以开一个二维数组visit[][]来标记。方法

不一。

AC代码：

#include<iostream>
using namespace std;

const int MAX=4;

char map[MAX][MAX];
int n,maxNum;   

void storeMap()   //存图
{
	for(int i=0;i<n;i++)
		cin>>map[i];
}

bool canPlace(int row,int col)   //判断是否可以放置
{                                 //在遇到墙之前同行或同列上已放置，则不能再放
	int i;

	for(i=col-1;i>=0;i--)
	{
		if(map[row][i]=='o') return false;
		if(map[row][i]=='X') break;
	}

	for(i=row-1;i>=0;i--)
	{
		if(map[i][col]=='o') return false;
		if(map[i][col]=='X') break;
	}

	return true;
}

void dfs(int i,int num)    //深搜，i代表已经搜索到的点，num代表该次搜索可以放得最多blockhouse
{                          //搜索完所有可能情况，每点'.'都会作为起点搜索一遍
	int row,col;

	if(i==n*n)
	{
		if(num>maxNum) maxNum=num;   //比较每遍搜索结果，保留当前最大值
		return;
	}
	else
	{
		row=i/n;    //从左到右，从上到下依次给每个点编号，1、2、...、n*n
		col=i%n;    //这是在取当前点所在图的行和列
		
		if(map[row][col]=='.' && canPlace(row,col))
		{
			map[row][col]='o';
			dfs(i+1,num+1);
			map[row][col]='.';
		}
		dfs(i+1,num);
	}
}

int main()
{
	while(cin>>n,n)
	{
		storeMap();

		maxNum=0;
		dfs(0,0);

		cout<<maxNum<<endl;
	}

	return 0;
}

目录

HDU1045-Fire-Net-暴力搜索DFS

HDU1045 Fire Net 暴力搜索DFS