D. Solve The Maze（思维+bfs）Codeforces Round ＃648 (Div. 2)

原题链接： ​ ​https://codeforces.com/problemset/problem/1365/D​​

测试样例：

输入
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#…
GG.
2 2
#B
B.
输出
Yes
Yes
No
No
Yes
Yes

样例解释

对于第一个和第二个测试用例，所有条件都已经满足。
对于第三个测试用例，只有1个空单元(2，2)，如果将他墙化那么在(1，2)处的好人将无法逃跑出来。
对于第四个测试案例，(1，1)的好人无法逃脱。
对于第五个测试用例，Vivek可以墙化单元格(2，3)和(2，2)。
对于最后一个测试用例，Vivek可以墙化目标单元格(2，2)。

题意： 给你一个迷宫，你可以将空单元变墙。要求你判断好人能不能全部出来，坏人能不能都困在迷宫。

解题思路： 什么问题我们都要清楚问题的本意。这个题目是要让所有的好人全部出来，所有的坏人都困在迷宫，我们试想，如果要让坏人困在迷宫，那么我们就必须将它的四周都变成墙使得它绝对困在这里不能出去。这样处理之后是能达到目的的，如果不这样，好人途径了坏人的四周或者就在坏人的四周，那么坏人不就可以跟着好人走了吗？还有一种特殊情况，如果迷宫出口的上边和左边有坏人，那这也是不可能的。经过这个处理之后我们就可以杜绝坏人出去迷宫，对几种情况特判得出结果。之后，我们就是要判断所有好人能不能出来。如果我们以好人为第一角色开启bfs，那这是非常慢的，每一个好人都要进行一次。我们换种思考，如果我以迷宫出口为第一角色开启搜索，如果路线上能够遇到所有好人，那好人到迷宫出口就有路径，这样，我们的任务不就简单了吗？OK，具体看代码。

AC代码：

登录后复制

      
      

       
       /*
       
       

       
       

       
       *
       
       

       
       */
       
       

       
       #include<bits/stdc++.h> 
       
       //POJ不支持
       
       

       
       

       
       #define rep(i,a,n) for (int i=a;i<=n;i++)
       
       //i为循环变量，a为初始值，n为界限值，递增
       
       

       
       #define per(i,a,n) for (int i=a;i>=n;i--)
       
       //i为循环变量， a为初始值，n为界限值，递减。
       
       

       
       #define pb push_back
       
       

       
       #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
       
       

       
       #define fi first
       
       

       
       #define se second
       
       

       
       #define mp make_pair
       
       

       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       const 
       
       int 
       
       inf 
       
       = 
       
       0x3f3f3f3f;
       
       //无穷大
       
       

       
       const 
       
       int 
       
       maxn 
       
       = 
       
       1e2;
       
       //最大值。
       
       

       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       

       
       typedef 
       
       long 
       
       double 
       
       ld;
       
       

       
       typedef 
       
       pair
       
       <
       
       ll, 
       
       ll
       
       >  
       
       pll;
       
       

       
       typedef 
       
       pair
       
       <
       
       int, 
       
       int
       
       > 
       
       pii;
       
       

       
       //*******************************分割线，以上为自定义代码模板***************************************//
       
       

       
       

       
       int 
       
       t,
       
       n,
       
       m,
       
       flag,
       
       cnt1,
       
       cnt2;
       
       //t组测试样例，n*m的大小关系,flag判断可不可行。cnt1统计好人数，cnt2统计可以到达迷宫出口的好人数。
       
       

       
       char 
       
       maze[
       
       maxn][
       
       maxn];
       
       //迷宫
       
       

       
       bool 
       
       vis[
       
       maxn][
       
       maxn];
       
       

       
       int 
       
       go[
       
       4][
       
       2]
       
       ={{
       
       1,
       
       0},{
       
       0,
       
       1},{
       
       0,
       
       -
       
       1},{
       
       -
       
       1,
       
       0}};
       
       

       
       bool 
       
       change(){
       
       
  
       
       bool 
       
       flag
       
       =
       
       true;
       
       
  
       
       rep(
       
       i,
       
       0,
       
       n
       
       -
       
       1){
       
       
    
       
       rep(
       
       j,
       
       0,
       
       m
       
       -
       
       1){
       
       
      
       
       if(
       
       maze[
       
       i][
       
       j]
       
       ==
       
       'B'){
       
       
        
       
       if(
       
       i
       
       >
       
       0){
       
       
          
       
       if(
       
       maze[
       
       i
       
       -
       
       1][
       
       j]
       
       ==
       
       '.'){
       
       
            
       
       maze[
       
       i
       
       -
       
       1][
       
       j]
       
       =
       
       '#';
       
       
          }
       
       
          
       
       else 
       
       if(
       
       maze[
       
       i
       
       -
       
       1][
       
       j]
       
       ==
       
       'G'){
       
       
            
       
       flag
       
       =
       
       false;
       
       
            
       
       break;
       
       
          }
       
       
        }
       
       
        
       
       if(
       
       j
       
       >
       
       0){
       
       
          
       
       if(
       
       maze[
       
       i][
       
       j
       
       -
       
       1]
       
       ==
       
       '.'){
       
       
            
       
       maze[
       
       i][
       
       j
       
       -
       
       1]
       
       =
       
       '#';
       
       
          }
       
       
          
       
       else 
       
       if(
       
       maze[
       
       i][
       
       j
       
       -
       
       1]
       
       ==
       
       'G'){
       
       
            
       
       flag
       
       =
       
       false;
       
       
            
       
       break;
       
       
          }
       
       
        }
       
       
        
       
       if(
       
       i
       
       <
       
       n
       
       -
       
       1){
       
       
          
       
       if(
       
       maze[
       
       i
       
       +
       
       1][
       
       j]
       
       ==
       
       '.'){
       
       
            
       
       maze[
       
       i
       
       +
       
       1][
       
       j]
       
       =
       
       '#';
       
       
          }
       
       
          
       
       else 
       
       if(
       
       maze[
       
       i
       
       +
       
       1][
       
       j]
       
       ==
       
       'G'){
       
       
            
       
       flag
       
       =
       
       false;
       
       
            
       
       break;
       
       
          }
       
       
        }
       
       
        
       
       if(
       
       j
       
       <
       
       m
       
       -
       
       1){
       
       
          
       
       if(
       
       maze[
       
       i][
       
       j
       
       +
       
       1]
       
       ==
       
       '.'){
       
       
            
       
       maze[
       
       i][
       
       j
       
       +
       
       1]
       
       =
       
       '#';
       
       
          }
       
       
          
       
       else 
       
       if(
       
       maze[
       
       i][
       
       j
       
       +
       
       1]
       
       ==
       
       'G'){
       
       
            
       
       flag
       
       =
       
       false;
       
       
            
       
       break;
       
       
          }
       
       
        }
       
       
        
       
       if(((
       
       i
       
       +
       
       1
       
       ==
       
       n
       
       -
       
       1
       
       &&
       
       j
       
       ==
       
       m
       
       -
       
       1)
       
       ||(
       
       i
       
       ==
       
       n
       
       -
       
       1
       
       &&
       
       j
       
       +
       
       1
       
       ==
       
       m
       
       -
       
       1))
       
       &&
       
       cnt2
       
       !=
       
       0){
       
       
          
       
       flag
       
       =
       
       false;
       
       
          
       
       break;
       
       
        }
       
       
      }
       
       
    }
       
       
    
       
       if(
       
       !
       
       flag)
       
       break;
       
       
  }
       
       
  
       
       return 
       
       flag;
       
       
}
       
       

       
       bool 
       
       check(
       
       int 
       
       i,
       
       int 
       
       j){
       
       
  
       
       if(
       
       i
       
       <
       
       0
       
       ||
       
       j
       
       <
       
       0
       
       ||
       
       i
       
       >=
       
       n
       
       ||
       
       j
       
       >=
       
       m)
       
       
    
       
       return 
       
       false;
       
       
  
       
       if(
       
       maze[
       
       i][
       
       j]
       
       ==
       
       '#')
       
       
    
       
       return 
       
       false;
       
       
  
       
       if(
       
       vis[
       
       i][
       
       j])
       
       
    
       
       return 
       
       false;
       
       
  
       
       return 
       
       true;
       
       
}
       
       

       
       int 
       
       bfs(){
       
       
  
       
       memset(
       
       vis,
       
       false,
       
       sizeof(
       
       vis));
       
       
  
       
       int 
       
       sum
       
       =
       
       0;
       
       
  
       
       vis[
       
       n
       
       -
       
       1][
       
       m
       
       -
       
       1]
       
       =
       
       true;
       
       
  
       
       queue
       
       <
       
       pii
       
       > 
       
       q;
       
       
  
       
       q.
       
       push(
       
       mp(
       
       n
       
       -
       
       1,
       
       m
       
       -
       
       1));
       
       
  
       
       pii 
       
       temp1,
       
       head;
       
       
  
       
       while(
       
       !
       
       q.
       
       empty()){
       
       
    
       
       head
       
       =
       
       q.
       
       front();
       
       
    
       
       q.
       
       pop();
       
       
    
       
       rep(
       
       i,
       
       0,
       
       3){
       
       
      
       
       temp1.
       
       fi
       
       =
       
       head.
       
       fi
       
       +
       
       go[
       
       i][
       
       0];
       
       
      
       
       temp1.
       
       se
       
       =
       
       head.
       
       se
       
       +
       
       go[
       
       i][
       
       1];
       
       
      
       
       if(
       
       check(
       
       temp1.
       
       fi,
       
       temp1.
       
       se)){
       
       
        
       
       if(
       
       maze[
       
       temp1.
       
       fi][
       
       temp1.
       
       se]
       
       ==
       
       'G')
       
       
          
       
       sum
       
       ++;
       
       
        
       
       vis[
       
       temp1.
       
       fi][
       
       temp1.
       
       se]
       
       =
       
       true;
       
       
        
       
       q.
       
       push(
       
       temp1);
       
       
      }
       
       
    }
       
       
  }
       
       
  
       
       return 
       
       sum;
       
       
}
       
       

       
       int 
       
       main(){
       
       
  
       
       //freopen("in.txt", "r", stdin);//提交的时候要注释掉
       
       
  
       
       IOS;
       
       
  
       
       while(
       
       cin
       
       >>
       
       t){
       
       
    
       
       while(
       
       t
       
       --){
       
       
      
       
       cin
       
       >>
       
       n
       
       >>
       
       m;
       
       
      
       
       cnt2
       
       =
       
       0;
       
       
      
       
       rep(
       
       i,
       
       0,
       
       n
       
       -
       
       1){
       
       
        
       
       cin
       
       >>
       
       maze[
       
       i];
       
       
        
       
       rep(
       
       j,
       
       0,
       
       m
       
       -
       
       1){
       
       
          
       
       if(
       
       maze[
       
       i][
       
       j]
       
       ==
       
       'G')
       
       
            
       
       cnt2
       
       ++;
       
       
        }
       
       
      }
       
       
      
       
       if(
       
       !
       
       change()){
       
       
        
       
       cout
       
       <<
       
       "NO"
       
       <<
       
       endl;
       
       
        
       
       continue;
       
       
      }
       
       
      
       
       cnt1
       
       =
       
       bfs();
       
       
      
       
       if(
       
       cnt1
       
       ==
       
       cnt2)
       
       
        
       
       cout
       
       <<
       
       "YES"
       
       <<
       
       endl;
       
       
      
       
       else
       
       
        
       
       cout
       
       <<
       
       "NO"
       
       <<
       
       endl;
       
       
    }
       
       
  }
       
       
  
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.
       
       
43.
       
       
44.
       
       
45.
       
       
46.
       
       
47.
       
       
48.
       
       
49.
       
       
50.
       
       
51.
       
       
52.
       
       
53.
       
       
54.
       
       
55.
       
       
56.
       
       
57.
       
       
58.
       
       
59.
       
       
60.
       
       
61.
       
       
62.
       
       
63.
       
       
64.
       
       
65.
       
       
66.
       
       
67.
       
       
68.
       
       
69.
       
       
70.
       
       
71.
       
       
72.
       
       
73.
       
       
74.
       
       
75.
       
       
76.
       
       
77.
       
       
78.
       
       
79.
       
       
80.
       
       
81.
       
       
82.
       
       
83.
       
       
84.
       
       
85.
       
       
86.
       
       
87.
       
       
88.
       
       
89.
       
       
90.
       
       
91.
       
       
92.
       
       
93.
       
       
94.
       
       
95.
       
       
96.
       
       
97.
       
       
98.
       
       
99.
       
       
100.
       
       
101.
       
       
102.
       
       
103.
       
       
104.
       
       
105.
       
       
106.
       
       
107.
       
       
108.
       
       
109.
       
       
110.
       
       
111.
       
       
112.
       
       
113.
       
       
114.
       
       
115.
       
       
116.
       
       
117.
       
       
118.
       
       
119.
       
       
120.
       
       
121.
       
       
122.
       
       
123.
       
       
124.
       
       
125.
       
       
126.
       
       
127.
       
       
128.
       
       
129.
       
       
130.
       
       
131.
       
       
132.
       
       
133.
       
       
134.
       
       
135.
       
       
136.
       
       
137.
       
       
138.