题意是在 n*n 的方格中进行炮台的安置，炮台不能处于同一行或同一列（类似于八皇后问题），但若是炮台间有墙壁阻挡，则可以同时安置这对炮台。问图中可以安放的最大炮台数目。
用深搜的方法，若此处为空地，则分四个方向继续向下，若直到搜到墙壁或图外也没有搜到已放置的炮台，则可以在当前位置添加炮台，继续向下，反之则不能添加炮台，求出最大的炮台数即可。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int dir[4][2] = {1,0,0,1,-1,0,0,-1};//{0,1,0,-1,1,0,-1,0}; 4 int n,flag,ans,newx,newy,mp[6][6]; 5 char s[6]; 6 void dfs(int sum) 7 { 8 if(sum > ans) ans = sum; 9 for(int i = 1; i <= n; ++i) 10 for(int j = 1; j <= n; ++j) 11 { 12 if(mp[i][j] == 0) 13 { 14 flag = 1; 15 for(int k = 0; k < 4; ++k) 16 { 17 newx = i; 18 newy = j; 19 while(1) 20 { 21 newx += dir[k][0]; 22 newy += dir[k][1]; 23 if(mp[newx][newy] == 1||mp[newx][newy] == -1) break; 24 else if(mp[newx][newy] == 2) 25 { 26 flag = 0; 27 break; 28 } 29 } 30 31 } if(flag) 32 { 33 mp[i][j] = 2; 34 dfs(sum+1); 35 mp[i][j] = 0; 36 } 37 } 38 } 39 } 40 int main() 41 { 42 while(~scanf("%d",&n)&&n) 43 { 44 memset(mp,-1,sizeof(mp)); 45 for(int i = 1; i <= n; ++i) 46 { 47 scanf("%s",s+1); 48 for(int j = 1; j <= n; ++j) 49 { 50 if(s[j] == '.') mp[i][j] = 0; 51 else mp[i][j] = 1; 52 } 53 } 54 ans = 0; 55 dfs(0); 56 printf("%d ",ans); 57 } 58 return 0; 59 }