首页 > Web开发 > 详细

hdoj 1045 Fire Net 【DFS】

时间:2014-08-22 00:22:55      阅读:355      评论:0      收藏:0      [点我收藏+]

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

看了一个星期。。

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

代码:

#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】,布布扣,bubuko.com

hdoj 1045 Fire Net 【DFS】

原文:http://blog.csdn.net/shengweisong/article/details/38730443

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!