ZOJ 1002 Fire Net(dfs)

嗯...

 

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

 

ZOJ 1002 Fire Net(dfs)
 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代码

 

上一篇:ZOJ 2314 (无源汇有上下边界的可行流)


下一篇:HDU - 2222,HDU - 2896,HDU - 3065,ZOJ - 3430 AC自动机求文本串和模式串信息(模板题)