CF 1365D Solve The Maze

题意：给定一个n*m的地图，'.'空地，'#' 墙，'G'好人， 'B'坏人。问你存不存在一种方案，把若干空地变成'#'（人不能通过墙），使得所有好人能逃离地图，所有坏人不能逃离地图。（n,m）为出口，人存在的地方不能设置'#'，保证出口一开始是空地。

思路：

① G == 0 Yes。

② B的四个方向存在G No。

③ 把每个B的四个方向的'.'变成'#'（这里可能把出口变为'#'，则直接是"No"），然后从出口跑bfs，然后统计从（n,m）开始的bfs能不能跑到所有的'G'，能"Yes",不能"No"。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <string>
  6 #include <vector>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <stack>
 10 #include <map>
 11  
 12 using namespace std;
 13   
 14 #define ll long long
 15 #define pb push_back
 16 #define fi first
 17 #define se second
 18   
 19 const int N = 60;
 20  
 21 int mv_x[] = {1, -1, 0, 0};
 22 int mv_y[] = {0, 0, 1, -1}; 
 23 char mp[N][N];
 24 int vis[N][N];
 25 int n, m;
 26 struct node
 27 {
 28     int x, y;
 29 };
 30 
 31 bool check(int x, int y)
 32 {
 33     return x >= 0 && x < n && y >= 0 && y < m;
 34 }
 35 
 36 void bfs()
 37 {
 38     queue<node > que;
 39     if(mp[n - 1][m - 1] == '#') return;
 40     que.push({n - 1, m -1});
 41     while(!que.empty()){
 42         int now_x = que.front().x;
 43         int now_y = que.front().y;
 44         que.pop();
 45         if(vis[now_x][now_y]) continue;
 46         vis[now_x][now_y] = 1;
 47 
 48         for(int o = 0; o < 4; ++o){
 49             int dx = now_x + mv_x[o];
 50             int dy = now_y + mv_y[o];
 51 
 52             if(check(dx, dy) && !vis[dx][dy] && mp[dx][dy] != '#'){
 53                 que.push({dx, dy});
 54             }
 55         }
 56     }
 57 }
 58 
 59 void solve()
 60 { 
 61     int T;
 62     cin >> T;
 63     while(T--){        
 64         cin >> n >> m;
 65         for(int i = 0; i < n; ++i) cin >> mp[i];
 66 
 67         //好人人数
 68         int G = 0;
 69         for(int i = 0; i < n; ++i){
 70             for(int j = 0; j < m; ++j){
 71                 if(mp[i][j] == 'G') G++;
 72             }
 73         }
 74 
 75         //有无好坏相连
 76         int connect = 0;
 77         for(int i = 0; i < n; ++i){
 78             for(int j = 0; j < m; ++j){
 79                 if(mp[i][j] == 'B'){
 80                     for(int o = 0; o < 4; ++o){
 81                         int dx = i + mv_x[o];
 82                         int dy = j + mv_y[o];
 83 
 84                         if(!check(dx, dy)) continue;
 85                         if(mp[dx][dy] == 'G'){
 86                             connect = 1;
 87                             continue;
 88                         }
 89                         if(mp[dx][dy] == '.') mp[dx][dy] = '#';
 90                     }
 91                 }
 92             }
 93         }
 94         // cout << endl;
 95         // for(int i = 0; i < n; ++i){
 96         //     for(int j = 0; j < m; ++j){
 97         //         cout << mp[i][j] << " ";    
 98         //     }cout << endl;
 99         // }cout << endl;
100         memset(vis, 0, sizeof(vis));
101         bfs();
102         
103         //逃离人数统计
104         int escape = 0;
105         for(int i = 0; i < n; ++i){
106             for(int j = 0; j < m; ++j){
107                 if(mp[i][j] == 'G' && vis[i][j]) escape++;
108             }
109         }
110         // printf("G = %d  connect = %d escape = %d
", G, connect, escape);
111         // cout << "(ans) = ";
112         if(G == 0) cout << "Yes" << endl;
113         else if(connect == 1) cout << "No" << endl;
114         else if(G == escape) cout << "Yes" << endl;
115         else cout << "No" << endl;
116     }
117 }
118   
119 int main()
120 {
121     ios::sync_with_stdio(false);
122     cin.tie(0);
123     cout.tie(0);
124  
125     solve();
126  
127     return 0;
128 }