Submission #4717864

---

Source Code Expand

#include<iostream>
using namespace std;
const int N=510;
int n,m,x,y,x2,y2,flag=0,b[4]= {1,0,-1,0},c[4]= {0,1,0,-1};
char a[N][N];
bool p[N][N]= {0};
void dfs(int x3,int y3) {
	for(int i=0; i<4; i++) {
		int xx=x3+c[i],yy=y3+b[i];
		if(flag) return;
		if(xx==x2&&yy==y2) {
			flag=1;
			return;
		}
		if(xx>0&&xx<=n&&yy>0&&yy<=m&&!p[xx][yy]&&a[xx][yy]=='.') {
			p[xx][yy]=1;
			dfs(xx,yy);
			//以下来自题解 
			//这里不能将状态回归！
            //毕竟之前竟然到过这里那么这里的情况肯定已经全部搜我。我因为没有早些出坑，找了半天错就是不知道为啥TLE,:
		}
	}
	if(flag) return;
}
int main() {
	cin>>n>>m;
	int x,y;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
			if(a[i][j]=='s') {
				x=i;
				y=j;
			}//记录起点
			if(a[i][j]=='g') {
				x2=i;
				y2=j;
			}
		}
	}
	dfs(x,y);
	if(flag) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

//吃货殿下佑我AC此题！！

Submission Info

Judge Result