D.SolveTheMaze(dfs,贪心)jziwjxjd的博客-

$看上去很麻烦,但是要从这种题目中学会分类,学会找题目规律的$

看上去很麻烦,但是要从这种题目中学会分类,学会找题目规律的

$color{Red}{Ⅰ.当好人和坏人相邻,直接输出NO}$

Ⅰ.当好人和坏人相邻,直接输出NO

$因为按照要求好人一定能到(n,m)$

因为按照要求好人一定能到(n,m)

$那么坏人一定可以先走到好人的位置,然后像好人一样走到终点$

那么坏人一定可以先走到好人的位置,然后像好人一样走到终点

$color{Red}Ⅱ.否则,考虑加一些障碍.$

Ⅱ.否则,考虑加一些障碍.

$这里一个小技巧,加的障碍一定是有明显的规律的,毕竟只是D题啊!!$

这里分享一个小技巧,加的障碍一定是有明显的规律的,毕竟只是D题啊!!

$因为我们想让坏人出不去,所以我们用障碍围住坏人的上下左右$

因为我们想让坏人出不去,所以我们用障碍围住坏人的上下左右

$这样是最优的。因为不管怎样你一定要把坏人围成一圈围起来,否则坏人就能出去$

这样是最优的。因为不管怎样你一定要把坏人围成一圈围起来,否则坏人就能出去

$那么围大圈肯定不如围小圈,小圈影响范围更小$

那么围大圈肯定不如围小圈,小圈影响范围更小

$那么围完所有坏人后,用bfs判断每个好人是否能走到(n,m)$

那么围完所有坏人后,用bfs判断每个好人是否能走到(n,m)

$只要有1个走不到就输出NO$

只要有1个走不到就输出NO

$这里有一个小技巧$

这里有一个小技巧

$每个好人都去bfs太麻烦,时间复杂度太高$

每个好人都去bfs太麻烦,时间复杂度太高

$不如我们从(n,m)开始bfs,标记终点能到达的点$

不如我们从(n,m)开始bfs,标记终点能到达的点

$就可以O(1)判断好人能否到终点$

就可以O(1)判断好人能否到终点

#include <bits/stdc++.h> using namespace std; int t,n,m; int vis[59][59]; char a[59][59]; int q[5]={0,0,1,-1},w[5]={1,-1,0,0},flag=1; void run(int x,int y) {  for(int i=0;i<4;i++)  {   int nx=x+q[i],ny=y+w[i];   if(nx>=1&&ny>=1&&nx<=n&&ny<=m)   {    if(a[nx][ny]=='.') a[nx][ny]='#';    if(a[nx][ny]=='G') flag=0;   }  } } struct p{  int x,y; }; queue<p>sq; void bfs(int s,int d) {  while(!sq.empty()) sq.pop();  memset(vis,0,sizeof(vis));  vis[s][d]=1;  sq.push((p){s,d});  while(!sq.empty())  {   p u=sq.front();sq.pop();   for(int i=0;i<4;i++)   {    int nx=u.x+q[i],ny=u.y+w[i];    if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny])    {     if(a[nx][ny]!='#')     {      vis[nx][ny]=1;      sq.push((p){nx,ny});     }    }   }  } } int main() {  cin>>t;  while(t--)  {   flag=1;   cin>>n>>m;   for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++) cin>>a[i][j];   for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)    if(a[i][j]=='B') run(i,j);   memset(vis,0,sizeof(vis));   if(a[n][m]!='#') bfs(n,m);   for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)   {    if(a[i][j]=='G')    {     if(vis[i][j]) continue;     else flag=0;    }   }   if(flag) cout<<"YES"<<endl;   else cout<<"NO"<<endl;  } }