嗯...

 

题目链接：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364501

 

这道题是想出来则是一道很简单的dfs：

将一个4*4的地图给每一个点排序，如下图：

0  1  2  3

4  5  6  7

8  9  10  11

12 13 14 15

 

设一个点为第k个点，那么它的坐标为（k/n，k%n），根据这个进行dfs，当k == n * n是退出dfs。如果k < n *ｎ，就继续dfs，判断是否能放下，即要放的这个点为空地并且横、纵上都没有东西，最后注意回溯。

 

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int n, ans; 8 char g[5][5]; 9 10 inline bool canput(int x, int y){11     for(int i = x - 1; i >= 0 && g[i][y] != 'X'; i--){12         if(g[i][y] == 'O') return 0;13     }14     for(int i = y - 1; i >= 0 && g[x][i] != 'X'; i--){15         if(g[x][i] == 'O') return 0;16     }17     return 1;18 }19 20 inline void dfs(int k, int cnt){21     int x, y;22     if(k == n * n){23         if(cnt > ans) ans = cnt;24         return;25     }26     else{27         x = k / n;28         y = k % n;29         if(g[x][y] == '.' && canput(x, y)){30             g[x][y] = 'O';31             dfs(k + 1, cnt + 1);32             g[x][y] = '.';33         }34         dfs(k + 1, cnt);35     }36 }37 38 int main(){39     while(~scanf("%d", &n) && n){40         ans = 0;41         for(int i = 0; i < n; i++){42             for(int j = 0; j < n; j++){43                 cin >> g[i][j];44             }45         }46         dfs(0, 0);47         printf("%d\n", ans);48     }49     return 0;50 }