题意

图中有空白位置’.’，有墙’#’，有好人’G’，有坏人’B’，为墙的方块不能行走，只能往上下左右四个方向行走。可以在某些空白位置设置一些墙，使得坏人到达不了点(n,m)，好人能够全部到达(n,m)。

有可行方案输出Yes，反之输出No。保证点(n,m)一开始是空白的。

题解

想想所有坏人周围的单元。从这些单元不应该有任何路径到(n,m)。如果有来自任何这样的单元的路径，那么与该单元相邻的坏人也可以到达(n,m)。

• 如果有好人和坏人在相邻的牢房里，答案是“No”.

基于这个想法，我们可以阻止任何与坏人相邻的空牢房。假设有另一个解决方案，其中一个单元格(i,j)邻接坏人不需要被阻拦。仍然没有任何途径(i,j)到(n,m)。在那个解决方案中，我们仍然可以阻止(i,j)并不影响最终答案。

一个坏人就在(n,m)旁边。在这种情况下，(n,m)一定是被封锁了，现在没有人能逃脱。

• 如果至少有一个好人在场，答案是“NO”.

• 如果在封锁了坏人的邻近单元后，有一些好人无法逃脱，那么答案又是“不”.记录原本图中好人的数量good，再从点(n,m)开始搜索一次看能找到多少好人，记作cnt如果cnt==good，则好人全部能走到(n,m)，反之会有一些好人没法走到.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=55;
char g[N][N];
bool vis[N][N];
int n,m;

inline check(int a,int b)
{
    return a>=0 && a<n && b>=0 && b<m;
}

void init()
{
    memset(vis,0,sizeof vis);
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        init();
        cin>>n>>m;

        for(int i=0;i<n;i++) scanf("%s",g[i]);

        bool ok=1;
        int good=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j] == 'B')
                    for(int k=0;k<4;k++)
                    {
                        int a=i+dx[k],b=j+dy[k];
                        if(check(a,b))
                        {
                            if(g[a][b] == '.') g[a][b]='#';
                            else if(g[a][b] == 'G') ok=0;
                        }
                    }
                else if(g[i][j] == 'G') good++;

        if(g[n-1][m-1] == '#' && good > 0) ok=0;

        queue<PII> q;
        q.push({n-1,m-1});
        vis[n-1][m-1]=1;
        int cnt=0;
        while(q.size())
        {
            PII t=q.front();
            q.pop();

            for(int i=0;i<4;i++)
            {
                int a=t.first+dx[i],b=t.second+dy[i];
                if(check(a,b) && g[a][b] != '#' && !vis[a][b])
                {
                    if(g[a][b] == 'G') cnt++;
                    q.push({a,b});
                    vis[a][b]=1;
                }
            }
        }

        if(cnt != good)  ok=0;

        if(ok) puts("Yes");
        else puts("No");
    }
    //system("pause");
}