AtCoderにて深さ優先の問題(https://atcoder.jp/contests/atc001/tasks/dfs_a)
について、以下の再帰関数を使ったプログラムを提出したところ、どうしてもREとなってしまうテストケースが存在した。
def main():
h, w = map(int, input().split())
whole_map =[]
for i in range(h):
whole_map.append(list(input()))
s_h = -1
s_w = -1
g_h = -1
g_w = -1
seek = [[False for _ in range(w)] for _ in range(h)]
for i in range(h):
for j in range(w):
if whole_map[i][j] == "s":
s_h = i
s_w = j
if whole_map[i][j] == "g":
g_h = i
g_w = j
dfs( whole_map, seek, s_h, s_w)
if seek[g_h][g_w] == True:
print("Yes")
else:
print("No")
def dfs(whole_map, seek, h_idx, w_idx):
if h_idx < 0 or h_idx >= len(whole_map) or w_idx < 0 or w_idx >= len(whole_map[0]) or whole_map[h_idx][w_idx] == "#":
return
if seek[h_idx][w_idx] == True:
return
seek[h_idx][w_idx] = True
dfs(whole_map, seek, h_idx+1, w_idx)
dfs(whole_map, seek, h_idx-1, w_idx)
dfs(whole_map, seek, h_idx, w_idx+1)
dfs(whole_map, seek, h_idx, w_idx-1)
main()
pythonはデフォルトで再帰回数の上限が1000とのことで、それに引っかかっていた模様。
def main()前に再帰上限をセットする、以下を記載してACとなった。
※今回はMAX 500*500の深さのため250000をセット
import sys
sys.setrecursionlimit(250000)