pythonでdfs

dfsの勉強がしたいネコ

dfsの勉強がしたいよお 今回は教材として、この方の記事を参考にさせていただきます。

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita

解く問題はこれ

A - 深さ優先探索

ほぼ記事通りに、pythonで書いていきます

def dfs_grid(h, w):
    # true:巡回済み
    seen[h][w] = True
    for direction in range(4):
        # new_h,new_w
        nh = h + dx[direction]
        nw = w + dy[direction]
        #進めなかったり巡回済みだったりしたらスルー
        if (nh < 0 or nh >=H or nw < 0 or nw >=W):
            continue
        if field[nh][nw] == '#':
            continue
        if seen[nh][nw]:
            continue
        dfs_grid(nh, nw)



H,W=map(int, input().split())
field=[list(list(input())) for i in range(H)]

# 右、上、左、下
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

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

for h in range(H):
    for w in range(W):
        if field[h][w] == 's':
            sh, sw = h, w
        if field[h][w] == 'g':
            gh, gw = h, w


dfs_grid(sh,sw)

if(seen[gh][gw]):
    print('Yes')
else:
    print('No')

記事が分かり易すぎてすぐにdfsを実装できました、提出するぞ ......

reが出てしまいます

んーーー、reということはindexか、それとももっと何か他のことか、、 とネコのように悩んでいたら、神記事を見つけましたので、参考にさせていただきました

Python 競技プログラミング高速化tips (PythonでAtcoderをやる際に個人的に気を付けてること)

Pythonでは再帰限界が1000回まで決められているので、再帰を使う際はこの限界を上げてあげる必要があります。

だそうです。なるほど

以下のコードを記述すると、reが消えました！ネコ

pythonではあまり再帰は使わない方が良いかもしれません、、

import sys
sys.setrecursionlimit(4100000)

参考文献

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita　(drken - Qiita)

Python 競技プログラミング高速化tips (PythonでAtcoderをやる際に個人的に気を付けてること) (https://juppy.hatenablog.com/about)