Submission #3665120

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int m,n;
char maze[501][501];
bool vst[501][501];
int sx,sy,ex,ey;
bool flag=false;

void read(int &s){
	s=0;int t=1;
	int k=getchar();
	for(;k<'0'||k>'9';k=getchar()){
		if(k=='-') t=-1;
	} 
	for(;k>='0'&&k<='9';k=getchar()){
		s=(s<<1)+(s<<3)+'0';
	}
	s*=t;
	return;
}

void dfs(int x,int y){
	if(vst[x][y]) return;
	vst[x][y]=true;
	if(x==ex&&y==ey){
		flag=true;
		return;
	}
	if(x-1>0&&x-1<=m&&y>0&&y<=n&&maze[x-1][y]!='#'){
		dfs(x-1,y);
	}
	if(flag) return;
	if(x+1>0&&x+1<=m&&y>0&&y<=n&&maze[x+1][y]!='#'){
		dfs(x+1,y);
	}
	if(flag) return;
	if(x>0&&x<=m&&y-1>0&&y-1<=n&&maze[x][y-1]!='#'){
		dfs(x,y-1);
	}
	if(flag) return;
	if(x>0&&x<=m&&y+1>0&&y+1<=n&&maze[x][y+1]!='#'){
		dfs(x,y+1);
	}
	if(flag) return;
	vst[x][y]=false;
}

int main(){
	read(m);read(n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			maze[i][j]=getchar();
			if(maze[i][j]=='s'){
				sx=i;sy=j;
			} 
			if(maze[i][j]=='g'){
				ex=i;ey=j;
			}
		}
	}
	dfs(sx,sy);
	if(flag) printf("Yes");
	else printf("No");
	return 0;
}

Submission Info

Judge Result