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