Implementieren Sie die Suche nach Tiefenpriorität (DFS) und die Suche nach Breitenpriorität (BFS) in Python

Was ich getan habe

AtCoder Typical Contest 001 A - Ich habe versucht, die Suche nach Tiefenpriorität in Python zu implementieren. Da dieses Problem sowohl durch die Tiefensuche (DFS) als auch durch die Breitensuche (BFS) gelöst werden kann, haben wir beide implementiert. Zusätzlich wurde die Suche nach Tiefenpriorität mit einem Muster unter Verwendung einer rekursiven Funktion und einem Muster unter Verwendung eines Stapels (LIFO) implementiert.

DFS

Fall mit rekursiver Funktion

#Eine rekursive Funktion für die Suche nach Tiefenpriorität
import sys
sys.setrecursionlimit(10**7) #Einschränkungen für rekursive Funktionsaufrufe

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")

Fall mit Stapel

#Ein Suchstapel mit Tiefenpriorität(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

#Eine Warteschlange für die Suche nach Tiefenpriorität, die durch die Suche nach Breitenpriorität gelöst werden soll(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")