自分用メモ python dfs(ATC001-A)

5755 ワード
AtCoder 強化学習 Python 大学生 初心者 Python テキストリンク

AtCoder Typical Contest 001 A問題の解答(python3.8.2)

探索済みにしたところを壁と同じ記号にすることで二度と同じ場所を探索しなくなることを利用する．

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

#座標変更のためのlist
dX = [0,1,0,-1]
dY = [1,0,-1,0]

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

    c[x][y] = "#" #探索済みを示すためのマーキング
    
    for dx,dy in zip(dX,dY):
        dfs(x+dx,y+dy)

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

dfs(sx, sy)

#ここまでに可能なら処理が終わっている
print("No")

警告
Pypy3では再帰関数がかなり遅いうえ
メモリも大量に食ってTLE,MLEになるので
Python3を使用してください

この問題でTLE,MLEになった提出(Pypy)