题目链接
题目大意：
假设我们有一个正方形的城市，并且街道是直的。城市的地图是n行n列，每一个单元代表一个街道或者一块墙。
碉堡是一个小城堡，有四个开放的射击口。四个方向是面向北、东、南和西。在每一个口子上有一架机关枪。
假设子弹能够穿过任何距离，并且摧毁路上的碉堡。另一方面，子弹不能穿越墙。
我们的目标是在城市里设置足够多的碉堡，并且任何两个碉堡都不会互相摧毁。正确的配置是没有两个碉堡在相同的水平行或者垂直列上，除非碉堡之间有墙把它们分开。在这个问题中，我们将使用小的方形城市（最多4*4），它包含了墙，并且子弹不能穿越。
接下来的图片显示五张城市地图，第1张图片是空的布局，第2张和第3张图片显示了合法的配置，第4和第5张图片显示了非法的配置。对于这样的地形来说，碉堡的最大数是5；第2张图片显示了这个配置方案，但还有其他的配置方案。
你的任务是写一个程序，在给出的地图描述下，计算城市中可以合法放置的碉堡的最大数。
输入文件包含一个或者多个地图描述，0作为文件的结束。每个地图描述首行是城市的尺寸n，n最大为4。接下来的n行描述了地图的每一行，符号“."代表开放区域，大写的X代表墙。输入文件中没有空格。
每一个测试用例，最后输出一行为合法放置碉堡的最大数。
Sample input:
4.X......XX......2XX.X3.X.X.X.X.3....XX.XX4................0
Sample output:
51524
#include <stdio.h>int n, res,max;int chess[10][10];int juge(int x, int y){ ???int i, j; ???for (i = y; i >= 0; i--) ???{ ???????if (chess[x][i] == 1)return 0; ???????if (chess[x][i] == 2)break; ???} ???for (i = y; i < n; i++) ???{ ???????if (chess[x][i] == 1)return 0; ???????if (chess[x][i] == 2)break; ???} ???for (i = x; i >= 0; i--) ???{ ???????if (chess[i][y] == 1)return 0; ???????if (chess[i][y] == 2)break; ???} ???for (i = x; i < n; i++) ???{ ???????if (chess[i][y] == 1)return 0; ???????if (chess[i][y] == 2)break; ???} ???return 1;}void dfs(){ ???int i, j; ???if (res > max)max = res; ???for (i = 0; i < n; i++) ???{ ???????for (j = 0; j < n; j++) ???????{ ???????????if (!chess[i][j] && juge(i, j)) ???????????{ ???????????????chess[i][j] = 1; ????????????//选择在该点放碉堡 ???????????????res++; ???????????????dfs(); ???????????????chess[i][j] = 0; ????????????//选择在该点不放碉堡 ??????????????这种感觉有点像动态规划的思想 ???????????????res--; ???????????} ???????} ???}}int main(){ ???char str[10]; ???int i, j; ???while (scanf("%d", &n) != EOF, n) ???{ ???????max = 0; ???????for (i = 0; i < n; i++) ???????{ ???????????scanf("%s", str); ???????????for (j = 0; j < n; j++) ???????????{ ???????????????if (str[j] == ‘X‘)chess[i][j] = 2; ???????????????else chess[i][j] = 0; ???????????} ???????} ???????res = 0; ???????dfs(); ???????printf("%d\n", max); ???} ???return 0;}
2018-03-31
zoj 1002 Fire Net 碉堡的最大数量【DFS】
原文地址：https://www.cnblogs.com/00isok/p/8681213.html