ZOJ 1002 Fire Net（dfs）

爱被打了一巴掌 2023-06-04 13:58 5阅读 0赞

嗯...

题目链接：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，判断是否能放下，即要放的这个点为空地并且横、纵上都没有东西，最后注意回溯。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     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 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11515316.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/4730b59670ba4c938417fff35c845bae.png