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

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

label ：BFS.

The question ： Give me a maze ,‘#’ Represents a wall ,‘G’ Show good people ,’B‘ It means bad people , End at (n,m). Ask if you can add a wall to the open space , So that all good people can go to the end , All bad guys can't get to the end .

tips:
A. greedy , Consider adding walls where you can add walls around all the bad guys （ Surround the bad guys ）. If a bad man is next to a good man , Obviously NO（ Because where good people can go, bad people can go qwq）.
B. If there are no good people , Direct output YES（ You can directly block the end ）.【 But note that you can't output directly without bad people YES, Because good people may be blocked by walls 】.
C. Don't run to every good person BFS, This complexity is too high . Because if every good person can finally reach the end , Then run backwards from the end BFS, The number of good people that can pass should be the total number of good people . once BFS that will do .

#include<bits/stdc++.h>
#define m_p make_pair
using namespace std;

int n,m,t,cntgood;
int dir[4][2] = {
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};
vector<pair<int, int> > bad;
vector<pair<int, int> > :: iterator it;
char mp[55][55];

void init(){
    
	while(!bad.empty())		bad.pop_back();
	cntgood = 0;
}

int bfs(){
    
	if(mp[n][m] == '#')	return 0;
	int cnt = 0;
	bool vis[55][55] = {
    false};
	queue<pair<int, int> >q;
	q.push(m_p(n, m));
	while(!q.empty()){
    
		int xx = q.front().first, yy = q.front().second;	q.pop();
		if(vis[xx][yy])	continue;
		vis[xx][yy] = true;
		if(mp[xx][yy] == 'G')	cnt++;
		for(int k = 0; k < 4; ++k){
    
			int tx = xx + dir[k][0] , ty = yy + dir[k][1];
			if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#')	continue;
			q.push(m_p(tx, ty)); 
		}
	}
	return cnt;
}
void solve(){
    
	init();
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; ++i){
    
		getchar();
		for(int j = 1; j <= m; ++j){
    
			scanf("%c",&mp[i][j]);
			if(mp[i][j] == 'B')	bad.push_back(m_p(i,j)); 
			if(mp[i][j] == 'G')	cntgood++;
		}
	}
	if(!cntgood)	printf("Yes\n");
	else{
    
		for(it = bad.begin(); it != bad.end(); ++it){
    
			int x = it->first, y = it->second;
			for(int k = 0; k < 4; ++k){
    
				int tx = x + dir[k][0] , ty = y + dir[k][1];
				if(tx < 1 || tx > n || ty < 1 || ty > m)	continue;
				if(mp[tx][ty] == 'G'){
    
					printf("No\n");
					return ;
				}else if(mp[tx][ty] == '.')	mp[tx][ty] = '#';
			}
		}
		(bfs() == cntgood) ? printf("Yes\n") : printf("No\n");
	}
}

int main(){
    
	scanf("%d",&t);
	while(t--)
		solve();
	return 0;
}


/*bool bfs(int x, int y){ // Don't do that bfs, Run for everyone bfs Too slow  bool vis[55][55] = {false}; queue<pair<int, int> >q; q.push(m_p(x, y)); while(!q.empty()){ int xx = q.front().first, yy = q.front().second; q.pop(); if(xx == n && yy == m) return true; if(vis[xx][yy]) continue; vis[xx][yy] = true; for(int k = 0; k < 4; ++k){ int tx = xx + dir[k][0] , ty = yy + dir[k][1]; if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#') continue; q.push(m_p(tx, ty)); } } return false; }*/