[Python] DFS (Tiefenprioritätssuche) ATC001A

#In Python bleibt das Standardlimit für die Anzahl der rekursiven Verarbeitungen hängen. Ändern Sie es daher
import sys
sys.setrecursionlimit(1000000)

#Definition der rekursiven Funktion DFS
def dfs(x, y):
    #Kennzeichen
    d[x][y] = 1

    #Schleife in 4 Richtungen
    for i in range(4):
        X = x + dx[i]
        X = y + dy[i]

        #Stellen Sie fest, ob sich X und Y in der Stadt befinden, noch nie waren oder kein Zaun sind
        if 0 <= X and X < n and 0 <= Y and Y < m and d[X][Y] == 0 and c[X][Y] != "#":
                dfs(X, Y)

#Eingang
n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

#Ob es erreicht wurde (0 ist nicht erreicht, 1 ist erreicht)
d = [[0] * m for i in range(n)]

#4 Richtungen zu bewegen
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

#Starten Sie dfs vom Startpunkt aus
for i in range(n):
    for j in range(m):
        if c[i][j] == "s":
            dfs(i, j)

#Ob Sie den Zielpunkt erreicht haben
for i in range(n):
    for j in range(m):
        if c[i][j] == "g" and d[i][j]:
            print("Yes")
            exit()
print("No")

Recommended Posts