Submission #11319102

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define N 502
#define M 502
int n,m,i,j,sx,sy,gx,gy;
char maq[N][M];
int book[N][M];

bool check;

void dfs(int x, int y)
{
	if(check) return;
	
	if (gx==x&&gy==y){
		check = true;
		return;
	}
	
	int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
	int tx, ty, k;
	
	
	for (k=0;k<=3;k++)
	{

		tx = x+next[k][0];
		ty = y+next[k][1];
		
		if (tx<1||tx>n||ty<1||ty>m) continue;
		
		
		if (book[tx][ty]==0)
		{
			book[tx][ty]=1;
			dfs(tx, ty);
			book[tx][ty]=0;
		}
	}
}

int main()
{
	cin>>n>>m;
	
	for(i=1;i<=n;i++){
	for(j=1;j<=m;j++){
	cin>>maq[i][j];
	if (maq[i][j]=='#') {book[i][j]=1;}
	if (maq[i][j]=='s') {sx = i;sy = j;}
	if (maq[i][j]=='g') {gx = i;gy = j;}
		}
	}
	book[sx][sy]=1;
	dfs(sx, sy);
	if (check) {cout<<"Yes"<<endl;}
	else {cout<<"No"<<endl;}
	
	return 0;
}

Submission Info

Judge Result