1365D - Solve The Maze - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+5;
const int M=1e9+7;



int32_t main(){
ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

int tt;
cin>>tt;

while(tt--){


int n,m;
cin>>n>>m;

vector<vector<char>>grid(n,vector<char>(m));


for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>grid[i][j];

int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
      
        auto isValid=[&](int x,int y){
    if(x<0 || y<0 || x>=n || y>=m)
    return 0;
    return 1;
};

int ok=1;

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(grid[i][j]=='B'){
            for(int k=0;k<4;k++){
                int i1=i+dx[k],j1=j+dy[k];
                if(isValid(i1,j1)){
                    if(grid[i1][j1]=='G'){
                        ok=0;
                        break;
                    }
                    if(grid[i1][j1]=='.')
                    grid[i1][j1]='#';
                }
            }
        }
        if(!ok)
        break;
    }
    if(!ok)
    break;
}

// for(int i=0;i<n;i++){
//     for(int j=0;j<m;j++)
//     cout<<grid[i][j];
//     cout<<"\n";
// }
vector<vector<int>>vis(n,vector<int>(m));
if(!ok){
    cout<<"No\n";
    continue;
}
int cnt=0;
for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        if(grid[i][j]=='G' && !vis[i][j]){
            cnt++;
            if(cnt>1){
                ok=0;
                break;
            }
queue<pair<int,int>>q;

q.push({i,j});
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
      
    auto isValid=[&](int x,int y){
    if(x<0 || y<0 || x>=n || y>=m || vis[x][y] || grid[x][y]=='#')
    return 0;
    return 1;
};
        
        while(!q.empty())
        {
            auto [x,y]=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int nx=x+dx[i],ny=y+dy[i];
                if(isValid(nx,ny)){
                    
                    vis[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
        }
           
           if(!vis[n-1][m-1]){
               ok=0;
               break;
           } 
        }
    }
    if(!ok)
    break;
}


if(ok)
cout<<"Yes\n";
else
cout<<"No\n";
}
}