D. Solve the maze (thinking +bfs) codeforces round 648 (Div. 2)

Original link ： ​ ​https://codeforces.com/problemset/problem/1365/D​​

The test sample ：

Input
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#…
GG.
2 2
#B
B.
Output
Yes
Yes
No
No
Yes
Yes

Sample explanation

For the first and second test cases , All conditions have been met .
For the third test case , Only 1 Empty cells (2,2), If you wallify him, then in (1,2) The good people in this place will not be able to escape .
For the fourth test case ,(1,1) A good man cannot escape .
For the fifth test case ,Vivek You can wall cells (2,3) and (2,2).
For the last test case ,Vivek You can wall the target cell (2,2).

The question ： Here's a maze for you , You can turn an empty cell into a wall . Ask you to judge whether all the good people can come out , Can all the bad guys be trapped in a maze .

Their thinking ： We should be clear about the original meaning of any problem . This topic is to let all good people come out , All the bad guys are trapped in a maze , Let's imagine , If you want to trap the bad guys in a maze , Then we must turn all around it into walls so that it is absolutely trapped here and can't go out . After such treatment, the goal can be achieved , If not , Good people go around bad people or just around bad people , Then the bad guys can follow the good guys ？ There is another special case , If there are bad people on the top and left of the labyrinth exit , This is also impossible . After this treatment, we can prevent the bad guys from going out of the maze , The result of special judgment on several cases . after , We just want to judge whether all good people can come out . If we take good people as our first role bfs, So this is very slow , Every good man has to do it once . Let's think differently , If I start the search with the maze exit as my first role , If you can meet all the good people on the route , The good man has a path to the exit of the labyrinth , such , Our task is simple ？OK, See code for details .

AC Code ：

Log in and copy

      
      

       
       /*
       
       

       
       

       
       *
       
       

       
       */
       
       

       
       #include<bits/stdc++.h> 
       
       //POJ I won't support it 
       
       

       
       

       
       #define rep(i,a,n) for (int i=a;i<=n;i++)
       
       //i Is a cyclic variable ,a For the initial value ,n Is the limit value , Increasing 
       
       

       
       #define per(i,a,n) for (int i=a;i>=n;i--)
       
       //i Is a cyclic variable , a For the initial value ,n Is the limit value , Decline .
       
       

       
       #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;
       
       // infinity 
       
       

       
       const 
       
       int 
       
       maxn 
       
       = 
       
       1e2;
       
       // Maximum .
       
       

       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       

       
       typedef 
       
       long 
       
       double 
       
       ld;
       
       

       
       typedef 
       
       pair
       
       <
       
       ll, 
       
       ll
       
       >  
       
       pll;
       
       

       
       typedef 
       
       pair
       
       <
       
       int, 
       
       int
       
       > 
       
       pii;
       
       

       
       //******************************* Split line , The above is a custom code template ***************************************//
       
       

       
       

       
       int 
       
       t,
       
       n,
       
       m,
       
       flag,
       
       cnt1,
       
       cnt2;
       
       //t Group test sample ,n*m The size of the relationship ,flag Judge whether it is feasible .cnt1 Count the number of good people ,cnt2 Count the number of good people who can reach the exit of the maze .
       
       

       
       char 
       
       maze[
       
       maxn][
       
       maxn];
       
       // maze 
       
       

       
       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);// When submitting, you should comment out 
       
       
  
       
       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.