题目的意思是：给你一个n * n 的地图，“X” 表示墙，“.” 表示空地。
然后需要在这个地图上面放置碉堡，不能放在同一行或者同一列，除非有墙挡着。
我们可以用递归来实现深搜，因为 n 最大为4。对于每一个可以放置碉堡的地方，我们有两种选择，一种就是放上去，标记一下，另一种就是不放，进行下一个位置的放置。
如何判断是否可以放置碉堡呢？这个只需要向该位置的四个方向进行搜索，先向下搜，直到遇到“X”或者出了边界，以此类推进行向上向左向右。但是如果遇到有之前标记过的，，也就是放置了碉堡的（我标记的是“1”），就说明该位置不能放。
下面的是AC的代码：
#include <iostream>using namespace std;char map[5][5];int n, max1;//变量用max竟然CE，坑爹的OJint dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};void dfs(int ans){int i, j, k, flag;for(i = 0; i < n; i++){for(j = 0; j < n; j++){if(map[i][j] == '.'){int x, y; flag = 0;//标记是否可以放置for(k = 0; k < 4; k++)//四个方向{x = i + dir[k][0];y = j + dir[k][1];while(1){if(x < 0 || x >= n || y < 0 || y >= n || map[x][y] == 'X')break;if(map[x][y] == '1')//不能放flag = 1;x += dir[k][0];//一直往同一个方向进行搜索y += dir[k][1];}}if(!flag)//可以放置{map[i][j] = '1';//标记dfs(ans + 1);//递归map[i][j] = '.';//标记的复位}}}}if(max1 < ans)//找最大碉堡数max1 = ans;}int main(){//freopen("data.txt", "r", stdin);int i ,j;while(cin >> n && n){getchar();for(i = 0; i < n; i++)for(j = 0; j < n; j++)cin >> map[i][j];max1 = 0;dfs(0);cout << max1 << endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
悠然享受和大自然融合之乐。
