dfs求助REon#9
查看原帖
dfs求助REon#9
400205
basachenboming楼主2022/1/8 21:44
#include<bits/stdc++.h>
using namespace std;
char a[501][501];
int b[501][501];
int k;
int x,y,c,d,n,m;
int check;
bool p=0; 
void dfs(int x,int y)
{
        if(x==c&&y==d)
		{
		p=1;
		return; 	
		}   
		if(x-1>0&&x-1<=n&&y>0&&y<=m&&b[x-1][y]==1)
		{
			dfs(x-1,y);
		}
		if(x+1>0&&x+1<=n&&y>0&&y<=m&&b[x+1][y]==1)
		{
			dfs(x+1,y);
		}
		if(x>0&&x<=n&&y-1>0&&y-1<=m&&b[x][y-1]==1)
		{
			dfs(x,y-1);
		}
		if(x>0&&x<=n&&y+1>0&&y+1<=m&&b[x][y+1]==1)
		{
			dfs(x,y+1);
		}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=m;j++)
	{
		cin>>a[i][j];
		if(a[i][j]=='.')
		{
			b[i][j]=1;
		}
		if(a[i][j]=='#')
		{
			b[i][j]=0;
		}
		if(a[i][j]=='s')
		{
			b[i][j]=1;
			x=i;
			y=j;
		}
		if(a[i][j]=='g')
		{
			b[i][j]=1;
			c=i;
			d=j;
		}
	}
}
dfs(x,y);
if(p==0)
{
	cout<<"No"<<endl;
}
else cout<<"Yes"<<endl;
return 0;
}
2022/1/8 21:44
加载中...