Submission #6364974

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable:4996)

char map[505][505];
int went[505][505];
int homeX, homeY, shopX, shopY;
int height, width;

int DFS(int x,int y);

int main()
{
	int i,j;
	memset(went, 0, sizeof(went));
	while (scanf("%d %d",&height,&width)!=EOF)
	{
		for (i = 0; i < height; i++)
		{
			for (j = 0; j <= width; j++)
			{
				map[j][i] = getchar();
				if (map[j][i] == 's')
				{
					homeX = j;
					homeY = i;
				}
				if (map[j][i] == 'g')
				{
					shopX = j;
					shopY = i;
				}
			}
		}
		went[homeX][homeY]=1;
		if (DFS(homeX, homeY)==1)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	return 0;
}

int DFS(int x,int y)
{
	int moveX, moveY;
	if (x==shopX&&y==shopY)
	{
		return 1;
	}
	for ( moveX = -1; moveX<=1;moveX++ )
	{
		for (moveY = -1; moveY <= 1; moveY++)
		{
			if (moveX*moveY==0)
			{
				int endX, endY;
				endX = x + moveX;
				endY = y + moveY;
				if (endX<=width&&endY<=height&&endX>=0&&endY>=0&& went[endX][endY] != 1 && (map[endX][endY] == '.'|| map[endX][endY] == 'g'))
				{
					went[endX][endY] = 1;
					if (DFS(endX,endY)==1)
					{
						return 1;
					}
				}
			}		
		}
	}
	return 0;
}

Submission Info

Judge Result