dfs c++ 求调
查看原帖
dfs c++ 求调
807584
mengqifeng楼主2024/8/23 15:38
#include <iostream>
#include <stdio.h>
using namespace std;
int xt,yt;
bool flag=0;
string k[10000];
bool a[505][505];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
void dfs(int xn,int yn)
{
	if(k[xn][yn]=='g')flag=true;
	if(flag)return;
	if(a[xn][yn]==0)return;
	a[xn][yn]=0;
	int sx,sy;
	for(int i=0;i<4;i++)
	{
		if(xn>=xt||yn>=yt||yn==0||xn==0)continue;
		sx=xn+dx[i];
		sy=yn+dy[i];
		if(k[sx][sy]==false&&a[sx][sy]!='#')dfs(sx,sy);
	}
	return;
	
}
int main()
{
	cin>>xt>>yt;
	for(int i=0;i<xt;i++)cin>>k[i];		
	for(int i=0;i<xt;i++)
	{
		for(int j=0;j<yt;j++)
		{
			if(k[i][j]=='s')xt=i,yt=j;
			if(k[i][j]=='.')a[i][j]=true;
		}
	}
	dfs(xt,yt);
	if(flag)cout<<"Yes";
	else cout<<"No";
	
	
	
	return 0;
}
2024/8/23 15:38
加载中...