王子救公主 (计蒜客)一道简单DFS
蓝桥杯不能粘贴 只能截图。。
这道题目很简单,主要想清楚 只要存在王子和公主都能到达的点,王子就能救出公主(此时必定有一个时刻可以让他们相遇)
#include <bits/stdc++.h>
using namespace std;
const int M = 100000+100;
char mp[110][110];
int n,m,visw[110][110],visg[110][110];
void dfsw(int x,int y)
{
if(x<=n&&x>=1&&y>=1&&y<=m&&!visw[x][y]&&mp[x][y]!='#')
{
visw[x][y]=1;
dfsw(x+2,y);
dfsw(x-2,y);
dfsw(x,y+2);
dfsw(x,y-2);
}
return ;
}
void dfsg(int x,int y)
{
//printf("g %d %d\n",x,y);
if(x<=n&&x>=1&&y>=1&&y<=m&&!visg[x][y]&&mp[x][y]!='#')
{
visg[x][y]=1;
dfsg(x+1,y);
dfsg(x-1,y);
dfsg(x,y+1);
dfsg(x,y-1);
}
return ;
}
void dfsg()
{
}
int main()
{
int sx,sy,gx,gy,wx,wy;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='g')
gx=i,gy=j;
if(mp[i][j]=='w')
wx=i,wy=j;
}
dfsw(wx,wy);
dfsg(gx,gy);
int flag=0;
for(int i = 1;i <= n; i++)
for(int j=1;j<=m;j++)
{
if(visw[i][j]==1&&visg[i][j]==1)
flag=1;
}
if(flag)
puts("yes");
else
puts("no");
return 0;
}