hdoj 1045 Fire Net 【DFS】

题意:如果两个点要放在同一行或者同一列,那么两个点中间要有一个墙,否则的话只能放一个点,最后问你最多能放几个点。

看了一个星期。。

这道题的解法我还是第一次见,就是逐个逐个的来放置每个点,然后每经过一个点都判断一次,详情看代码

代码:

#include <stdio.h>
#include <string.h>
int ans, n;
char map[10][10];
int judge(int lin, int row)
{
	int i;
	for(i = lin-1; i >= 0; i --){  //判断所在列
		if(map[i][row] == 'a') return false;
		if(map[i][row] == 'X') break;
	}
	for(i = row-1; i >= 0; i --){ //判断所在行
		if(map[lin][i] == 'a') return false;
		if(map[lin][i] == 'X') break; 
	}
	return true;
}
void dfs(int cou, int max)
{
	if(cou == n*n){
		ans = ans > max?ans:max;
		//printf("%d..\n", max);
		return;
	}
	else{
		int lin = cou/n;//这里很精巧,仔细体会一下
		int row = cou%n;
		if(map[lin][row] == '.'&&judge(lin, row)){
			map[lin][row] = 'a';
			dfs(cou+1, max+1);
			map[lin][row] = '.';
		}
		dfs(cou+1, max);
	}
}
int main()
{
	int i, j;
	while(scanf("%d", &n), n){
		memset(map, 0, sizeof(map));
		for(i = 0; i < n; i ++){
			scanf("%s", map[i]);
		}
		ans = 0;
		dfs(0, 0);
		printf("%d\n", ans);
	}
	return 0;
} 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1045

hdoj 1045 Fire Net 【DFS】,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。