Submission #7106848

---

Source Code Expand

# ACT1
# DFSを用いた探索

import sys
sys.setrecursionlimit(10**6) 

H ,W = map(int, input().split())

maze = [[] for _ in range(H)]

for i in range(H):
	maze[i] = input()


reached = [[False for i in range(W)] for j in range(H)]


for i in range(H):
	if "s" in maze[i]:
		s_y = maze[i].index("s")
		s_x = i
		break





def serach_children(x,y):
	children = []
	if x >= 0 and x <=H-1 and y>= 0 and y <= W-1:
		if reached[x-1][y] == False and reached[x-1][y] != "#":
			children.append((x-1,y))
		if reached[x][y-1] == False and reached[x][y-1] != "#":
			children.append((x,y-1))
		if reached[x+1][y] == False and reached[x+1][y] != "#":
			children.append((x+1,y))
		if reached[x][y+1] == False and reached[x][y+1] != "#":
			children.append((x,y+1))

	return children[0]




def search(x, y):
	# スタックにはタプルでx,y座標を入れる
	stack = []

	reached[x][y] = True
	stack.append((x,y))
	while stack != []:
		node = stack.pop(-1)
		if maze[node[0]][node[1]] == "g":
			return True
			break
		else:
			# childは周囲４マスで訪れていないところand"#"でないところの１つのタプル
			child = serach_children(x,y)
			if child == []:
				stack.remove(-1)
			else:
				reached[child[0]][child[1]] = True
				stack.append((child[0],child[1]))

	if stack == []:
		return False			



if search(s_x, s_y):
	print("Yes")
else:
	print("No")	

Submission Info

Judge Result