Lösen Sie mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (024 --027 Suche nach Tiefenprioritäten)

1. Zweck

Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.

Dieser Artikel ist "024-027 Depth Priority Search".

2. Zusammenfassung

Es ist einfach, in den folgenden Artikel zu schreiben, aber ich habe lange gebraucht, um `` BFS``` und `DFSzu verstehen.bfsWanndfs```の基本形をおさえるまでに、最初は解説を読んでもまったくわからず、理解するまでに1週間くらい（1日10時間以上悩むこWannもあった）かかっています。

Natürlich habe ich den Kommentar gelesen, um zu verstehen, aber ich habe versucht, den Code zu debuggen, der durch `` `AC``` geht, und zu sehen, wie die Daten Zeile für Zeile funktionieren. Ich tat es, bis ich begriff, dass ich es bestätigen würde. Was die Wiederholung betrifft, habe ich tatsächlich alle rekursiven Berechnungen in eine Notiz geschrieben.

Dann wurde irgendwann die Datenstruktur von `BFS``` und` `DFS``` in meinem Kopf erstellt, und selbst wenn ich nichts in das Notizbuch schrieb, dachte ich` Es war möglich, Daten wie BFS, `` `DFS zu verschieben. Vielleicht kommt dieser Moment je nach Individuum, aber ich denke, dass er nicht ohne ein gewisses Maß an Denken (Versuch?) Kommen wird.

Darüber hinaus verwendet das Debugging den Entwickler von VS-Code. Praktisch. So was.

3. Hauptgeschichte

024 --027 Suche nach Tiefenpriorität

024. ALDS_11_B - Tiefe Prioritätssuche

Antworten

N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
    i, num, *nodes = map(int, input().split())
    graph[i] = nodes #Gerichteter Graph

go_time = [0] * (N+1)
back_time = [0] * (N+1)

def dfs(node, t):
    #Aufzeichnung des Gehens
    t += 1
    go_time[node] = t
    for next_node in graph[node]:
        if go_time[next_node] == 0:
            t = dfs(next_node, t)
    #Aufzeichnung der Rückkehr
    t += 1
    back_time[node] = t
    return t

t = 0
for node in range(1, N+1): #Versuchen Sie, von allen Punkten aus zu beginnen
    if go_time[node] == 0:
        t = dfs(node, t)
    print(node, go_time[node], back_time[node])

Erstens ist das Empfangen von Daten mühsam. In Bezug auf den Empfang von Diagramminformationen ist der Ort, an dem die Länge variabel ist, der letzte wie i, num, * node = map (int, input (). Split ()) Sie können den Rest an Knoten``` übergeben, indem Sie * zu * Knoten` `` hinzufügen. Referenz-> Beispiele und Listen in Python entpacken (erweitern und mehreren Variablen zuweisen)

Wie Sie sehen können, können Sie einige Teile nicht erreichen, selbst wenn Sie bei 1 beginnen (ich weiß nicht, wo Sie dies in der Problemstellung lesen können ...). Versuchen Sie also alle Punkte als Kandidaten für den Start wird gebraucht.

Sowohl `dfs``` durch diesmal rekursives Schreiben als auch` dfs durch `` `deque (im Fall von Python) müssen sich zuerst den Basistyp und die Erklärung des Basistyps merken Ist ziemlich schwierig für mich, also werde ich es weglassen. Vorerst werde ich diese Grundform lernen und zunächst fortfahren.

025. AOJ 1160 - Wie viele Inseln gibt es?

Antworten

from collections import deque

def main(w, h, MAP, visited):
    count = 0
    #Versuchen Sie, von allen Punkten aus zu beginnen
    for start_y in range(h):
        for start_x in range(w):
            if MAP[start_y][start_x] == 0: #Überspringen Sie im Falle des Meeres
                continue
            if visited[start_y][start_x] != -1: #Überspringen Sie die Suche
                continue
            q = deque()
            q.append((start_y, start_x))
            visited[start_y][start_x] = 1
        
            while q:
                y, x = q.pop()

                for dy in range(-1, 2):
                    for dx in range(-1, 2):
                        moved_y = y + dy
                        moved_x = x + dx

                        if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Überspringen Sie das Verlassen der Karte
                            continue
                        if MAP[moved_y][moved_x] == 0: #Überspringen Sie im Falle des Meeres
                            continue
                        if visited[moved_y][moved_x] != -1: #Überspringen Sie die Suche
                            continue
                        visited[moved_y][moved_x] = 1
                        q.append((moved_y, moved_x))
            
            count += 1 #Eine Insel nach der Durchreise
    return count

if __name__ == "__main__":

    answer_list =[]
    while True:
        w, h = map(int, input().split())
        MAP = [list(map(int, input().split())) for _ in range(h)]
        visited = [[-1] * w for _ in range(h)]

        if w == 0 and h == 0:
            break
        
        answer = main(w, h, MAP, visited)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)

Persönlich ist es einfacher, `dfs``` per Deck zu schreiben (decue?) Als rekursiv. Dies ist auch die Grundform von `dfs``` (glaube ich), also schreibe es einfach so wie es ist.

26. AtCoder Beginner Contest 138 D - Ki

Antworten

from collections import deque
# -------------- [Eingang] --------------
N, Q = map(int, input().split()) #N ist die Anzahl der Eckpunkte, Q ist die Anzahl der Operationen
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

counts = [0] * (N+1)
for _ in range(Q):
    p, x  = map(int, input().split())
    counts[p] += x
visited = [-1] * (N+1)
# -------------- [Beginnen Sie mit 1] --------------
q = deque()
q.append(1)
visited[1] = 1
# -------------- [DFS] --------------
while q:
    node = q.pop()

    next_nodes = graph[node]
    for next in next_nodes:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = 1
        counts[next] += counts[node] #Fügen Sie die elterliche Punktzahl hinzu

print(*counts[1:])

Dieses Problem ist AtCoder Anfängerwettbewerb 176 D - Assistent in Labyrinth (Klicken Sie hier für meinen Antwortartikel → AtCoder ABC 176 Python (A ~ E) )) Ich fand es ein bisschen so. Dieses Problem ist einfacher, aber ...

Was ähnlich ist, ist `zählt [weiter] + = zählt [Knoten]` in diesem Teil, `besucht [bewegt_y] [bewegt_x] = besucht [in ABC 176] y] [x] `Hier.

Der Grund, warum ich dachte, dass es ähnlich ist, ist, wenn ich von dem mit `q.pop ()` extrahierten Suchziel (nennen wir es ①) zum Suchziel (nennen wir es ②) neben dem Suchziel moving gehe. Dies liegt daran, dass der Prozess des Aktualisierens der Informationen in (2) unter Verwendung der Informationen in (1) ähnlich ist.

In normalen (?) `DFS``` und BFS denke ich, dass die Aktualisierung der Informationen in ② oben oft eine andere Liste oder nur ein Inkrement ist, aber dieselbe Liste Ich dachte, es wäre schwierig, die Methode zur Aktualisierung der oben genannten Informationen zu finden, wenn ich es nicht einmal tun würde. Sobald Sie diesen Punkt verstanden haben, unterscheidet sich der Rest nicht wesentlich von der Grundform von `` `BFS.

027. JOI 2009 Qualifying 4-Thin Ice Crossing

Antworten

import sys
sys.setrecursionlimit(10**9)

# -------------- [Ursprünglicher Wert] --------------
def dfs(count, start_y, start_x, visited):
    ans = count
    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx
        if moved_y < 0 or n-1 < moved_y or moved_x < 0 or m-1 < moved_x:
            continue
        if grid[moved_y][moved_x] == 0:
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[start_y][start_x] = 1
        ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) #Holen Sie sich den Maximalwert, der vom Startpunkt aus erreicht werden kann
        visited[start_y][start_x] = -1
    
    return ans


if __name__ == "__main__":
    # -------------- [Eingang] --------------
    m = int(input()) #Seite
    n = int(input()) #Vertikal
    grid = [list(map(int, input().split())) for _ in range(n)] # 1:Eis, 0:Kein Eis
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Nur oben, unten, links und rechts
    visited = [[-1] * m for _ in range(n)]
    # -------------- [Probieren Sie alle Punkte als Ausgangspunkt aus] --------------
    answer = 0
    for start_y in range(n):
        for start_x in range(m):
            if grid[start_y][start_x] == 0:
                continue
            answer = max(answer, dfs(1, start_y, start_x, visited))

    print(answer)

sys.setrecursionlimit(10**9)Sie können ohne es passieren, aber ich werde es als Erinnerung verlassen.

 Dies ist fast das gleiche wie die Grundform, aber der Unterschied ist

```python

ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) #Holen Sie sich den Maximalwert, der vom Startpunkt aus erreicht werden kann
visited[start_y][start_x] = -1

Nur hier. Dies gibt die längste Entfernung von jedem Startpunkt zurück.