Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python

Ce que j'ai fait

AtCoder Typical Contest 001 A - J'ai essayé d'implémenter la recherche de priorité de profondeur en python. Étant donné que ce problème peut être résolu à la fois par Depth First Search (DFS) et Breadth First Search (BFS), nous avons implémenté les deux. De plus, la recherche de priorité de profondeur a été implémentée avec un modèle utilisant une fonction récursive et un modèle utilisant une pile (LIFO).

DFS

Cas utilisant la fonction récursive

#Une fonction récursive de recherche de priorité de profondeur
import sys
sys.setrecursionlimit(10**7) #Restrictions d'appel de fonction récursives

def dfs(v_x, v_y, seen_list, c_list):
    if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
        return
    if seen_list[v_y][v_x]:
        return
    if c_list[v_y][v_x] == "#":
        return
    seen_list[v_y][v_x] = True
    dfs(v_x+1,v_y,seen_list,c_list)
    dfs(v_x-1,v_y,seen_list,c_list)
    dfs(v_x,v_y+1,seen_list,c_list)
    dfs(v_x,v_y-1,seen_list,c_list)
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

dfs(s[0],s[1],seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

Cas utilisant la pile

#Une pile de recherche prioritaire en profondeur(LIFO)
from collections import deque

def dfs(stack, seen_list, c_list):
    while len(stack)>0:
        v_x, v_y = stack.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        stack.append([v_x+1,v_y])
        stack.append([v_x-1,v_y])
        stack.append([v_x,v_y+1])
        stack.append([v_x,v_y-1])
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
stack = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

stack.append(s)
dfs(stack,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

BFS

#Une file d'attente de recherche de priorité de profondeur à résoudre par la recherche de priorité de largeur(FIFO)
from collections import deque

def bfs(que, seen_list, c_list):
    while len(que)>0:
        v_x, v_y = que.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        que.appendleft([v_x+1,v_y])
        que.appendleft([v_x-1,v_y])
        que.appendleft([v_x,v_y+1])
        que.appendleft([v_x,v_y-1])
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
que = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

que.append(s)
bfs(que,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")