D. Solve The Maze Codeforces Round 648 (Div. 2)

题目链接：

Problem - 1365D - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/problemset/problem/1365/D

题目大意：

有一张地图n行m列（地图外面全是墙），里面有好人（G），坏人（B），道路（.）,墙（#），出口在n,m，人可以往上下左右走（不论好坏）。

你可以把道路变成墙，问你是否可以把所有的坏人封住，让所有的好人逃出？

思路：

地图有4种情况。但无所谓咱们又不是对4种情况去判断。

把坏人周围4格的道路封住，最后从终点去看所有的好人能不能到这里，有没有坏人能到这。

方法：

在读入图之后，遍历每一个点，遍历到坏人时，在周围4格尝试建墙。

最后用bfs查询：

bool bfs(){//寻找能出去的好人个数,有没有坏人能出去 ll sum=0;//能出去的好人个数 bool f=1;//因为只要有坏人出去就不行,直接用bool memset(vis,0,sizeof vis);//每次清空 while(!q.empty()){ll x=q.front().first,y=q.front().second;//取点 q.pop();if(vis[x][y])continue;vis[x][y]=1;//标记已经来过 if(mp[x][y] == 'G')sum++;if(mp[x][y] == 'B')f=0;for(ll i = 0 ; i < 4 ; i ++){//查询下一个点 ll tx = x + dir[i][0];ll ty = y + dir[i][1];if(tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || mp[tx][ty] == '#')continue;q.push({tx,ty});}}return sum == g && f;//好人全部能出去,没有坏人出去 
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"const ll N = 1e2+7;
ll n,m,g;
char mp[N][N];//存图 
bool vis[N][N];//标记走过的路 
ll dir[4][2]={0,1,1,0,0,-1,-1,0};//方向数组 
queue<pair<ll,ll> >q;//接下来要走的地方 bool bfs(){//寻找能出去的好人个数,有没有坏人能出去 ll sum=0;//能出去的好人个数 bool f=1;//因为只要有坏人出去就不行,直接用bool memset(vis,0,sizeof vis);//每次清空 while(!q.empty()){ll x=q.front().first,y=q.front().second;//取点 q.pop();if(vis[x][y])continue;vis[x][y]=1;//标记已经来过 if(mp[x][y] == 'G')sum++;if(mp[x][y] == 'B')f=0;for(ll i = 0 ; i < 4 ; i ++){//查询下一个点 ll tx = x + dir[i][0];ll ty = y + dir[i][1];if(tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty] || mp[tx][ty] == '#')continue;q.push({tx,ty});}}return sum == g && f;//好人全部能出去,没有坏人出去 
}void solve(){cin >> n >> m;memset(mp,'#',sizeof mp);g=0;//好人的个数重置 for(ll i = 1 ; i <= n ; i ++)for(ll j = 1 ; j <= m ; j ++){cin >> mp[i][j];if(mp[i][j] == 'G')g++;}for(ll i = 1 ; i <= n ; i ++)for(ll j = 1 ; j <= m ; j ++)if(mp[i][j] == 'B')for(ll k = 0 ; k < 4 ; k ++){ll x = i + dir[k][0];ll y = j + dir[k][1];if(x < 1 || y < 1 || x > n || y > m || mp[x][y] != '.')continue;mp[x][y]='#';}if(mp[n][m] == '#'){//如果终点被封上了 g == 0 ? cout << "Yes" << endl : cout << "No" << endl;return;}q.push({n,m});bfs() ? cout << "Yes" << endl : cout << "No" << endl;return;
}int main(){ll t=1;cin >> t;while(t --)solve();return 0;
}