pythonで深さ優先探索

Question

問題文

深さ優先探索の問題です

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

https://atcoder.jp/contests/atc001/tasks/dfs_a

発生している問題・エラーメッセージ

atcoderで提出するといくつかREが出ます。入力例ではすべてACなのでどうしてエラーなのか分かりません。

code

import numpy as np
import sys

h,w = map(int, input().split())
c = [list(input()) for i in range(h)]
c = np.array(c)
c = np.pad(c, 1, 'constant') #周辺を壁の代わりに０で囲う


def search(x,y):
  if c[x][y] == '#' or c[x][y] == '0':
    return #壁または外周だったら戻る
  elif c[x][y] == 'g':
    print('Yes')
    sys.exit()
  else:
    c[x][y] = '#'
    search(x+1, y)
    search(x-1, y)
    search(x, y+1)
    search(x, y-1)

s = np.argwhere(c=='s') #スタート地点を探す
search(s[0][0], s[0][1])
print('No')

試したこと

search(x-1, y)を消すとREではなくWAがでました。

補足情報（FW/ツールのバージョンなど）

手がかりがなく困っています。誤っている箇所がわかる方、Atcoder Typical Condest 001　のサンプルコードのサイトがわかる方がいらっしゃいましたら宜しくお願いします。

Answer 1

再帰の上限というものがあり、それに引っかかていたようです。
sys.setrecursionlimit
を最初に記載したら通りました。
ご回答くださった方ありがとうございました。

Answer 2

通った経路を塀（#）に書き換えながら探索してますが、途中で失敗したとき、
バックトラックで高橋君の位置は戻るものの、書き換えた塀を道に戻していません。

Comments

[Mmaple]

ご回答ありがとうございます。こちらのブログを参考にコードを書いてみたのですが、参考にしたコードでも書き直しは行っていないように見受けられます。私のものと何が違うのでしょうか。
https://nashidos.hatenablog.com/entry/2020/01/04/234842#%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%81%A7%E5%AE%9F%E8%A3%85

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = map(int,input().split())
c = [list(input()) for i in range(h)]

def dfs(x,y):
if not(0 <= x < h) or not(0 <= y < w) or c[x][y] == "#": # 壁に当たったり、探索範囲外になった場合はreturn
return
if c[x][y] == "g": # ゴールを見つけたら”Yes”を出力して終了
print("Yes")
sys.exit()

c[x][y] = "#" #探索済みを示すためのマーキング
dfs(x+1,y)
dfs(x-1,y)
dfs(x,y+1)
dfs(x,y-1)

for i in range(h):
for j in range(w):
if c[i][j] == "s":
sx, sy = i, j # スタート位置

dfs(sx, sy)
print("No")