CF1365D Solve The Maze 题解（注：本题目及题解均尚未完成！

description：

求能否在一个 $n\times m$ 的矩阵中设置一些墙使得所有好人都能到达 $(n,m)$，而所有坏人都不能。

solution：

我们只需要判断每个好人能否在不经过坏人的情况下到达终点即可（如果在途中与坏人相邻则同样不能到达）。

有一个剪枝就是将连在一起的好人仅保留一个而其他都看做空地，可减少 dfs 的次数。

code：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char a[55][55];
int sx[5]={0,-1,1,0,0};
int sy[5]={0,0,0,-1,1};
int vis[55][55];
int n,m;
int dfs(int xx,int yy)
{
	for(int i=1;i<=4;i++)
	{
		int x=xx+sx[i];
		int y=yy+sy[i];
		if(a[x][y]=='B')
		{
			return 0;
		}
	}
	if(xx==n&&yy==m)return 1;
	for(int i=1;i<=4;i++)
	{
		int x=xx+sx[i];
		int y=yy+sy[i];
		if(vis[x][y]==0&&(a[x][y]=='G'||a[x][y]=='.'))
		{
			vis[x][y]=1;
			if(dfs(x,y))
			{
				vis[x][y]=0;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
			}
		}
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]=='G')
				{
					if(a[i][j-1]=='G'||a[i][j+1]=='G'||a[i-1][j]=='G'||a[i+1][j]=='G')
					{
						if(a[i][j-1]!='B'&&a[i][j+1]!='B'&&a[i-1][j]!='B'&&a[i+1][j]!='B')
						{
							a[i][j]='.';
							continue;
						}
					}
					memset(vis,0,sizeof(vis));
					
					if(dfs(i,j)==0)
					{
						printf("No\n");
						flag=1;
						break;
					}
				}
				
			}
			if(flag==1)
				break;
		}
		if(flag==0)
		{
			printf("Yes\n");
		}
	}
	return 0;
}