Lösen Sie mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (028 - 033 Suche nach Breitenpriorität)

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 "028 - 033 Width Priority Search".

2. Zusammenfassung

dfsWenn möglichbfsIst fast das gleiche. Der Unterschied besteht darin, dass `deque ()` aus `pop ()` `in DFSherausspringt Verwenden Sie.

3. Hauptgeschichte

028 --033 Suche nach Breitenpriorität

028. ALDS_11_C - Suche mit breiter Priorität

Antworten

from collections import deque

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

q = deque()
q.append(1)
visited[1] = 0

while q:
    node = q.popleft()

    for next in graph[node]:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = visited[node] + 1
        
for i, num in enumerate(visited[1:]):
    print(i+1, num)

Dies ist ein Grundproblem. Wenn Sie hier Ihre eigene Form herstellen, können Sie andere Probleme mit nur wenigen Anpassungen lösen.

bfsWenn Sie grob den Fluss von zeigen

1. Verwenden Sie "besucht", um eine Liste der Suchziele zu erstellen.
2. Bereiten Sie vorerst `deque ()` vor und geben Sie den Anfangswert ein
3. Drehen Sie `while```, bis` deque () `` `leer ist
4. Verwenden Sie `popleft ()`, um den Wert first in first out abzurufen
5. Untersuchen Sie das Diagramm anhand der abgerufenen Werte, um das Ziel zu finden
6. Stellen Sie fest, ob das Ziel gesucht wurde
7. Aktualisieren Sie `Anhängen``` und` besucht```, wenn Sie nicht suchen

ist.

029. AtCoder-Anfängerwettbewerb 007 C - Breitensprioritätssuche

Antworten

from collections import deque

R, C = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1 #Auf 0 Index festgelegt
sx -= 1
gy, gx = map(int, input().split())
gy -= 1 #Auf 0 Index festgelegt
gx -= 1
grid = [list(input()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((sy, sx))
visited[sy][sx] = 0

while q:
    start_y, start_x = q.popleft()

    for dy, dx in moves:
        moved_y = start_y + dy
        moved_x = start_x + dx

        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue
        visited[moved_y][moved_x] = visited[start_y][start_x] + 1
        q.append((moved_y, moved_x))

print(visited[gy][gx])

Dies ist typisch für das Typische. Ich werde mich vorerst daran erinnern.

030. JOI 2011 Qualifying 5-Cheese

Antworten

from collections import deque

def bfs(start_y, start_x, target_cheese, H, W, grid):

    visited = [[-1] * W for _ in range(H)]
    moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    q = deque()
    q.append((start_y, start_x))
    visited[start_y][start_x] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            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:
                continue
            if grid[moved_y][moved_x] == 'X':
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            if grid[moved_y][moved_x] == target_cheese:
                visited[moved_y][moved_x] = visited[y][x] + 1
                return visited[moved_y][moved_x]
 
            visited[moved_y][moved_x] = visited[y][x] + 1
            q.append((moved_y, moved_x))
            

if __name__ == "__main__":
    H, W, N = map(int, input().split())
    grid = [list(input()) for _ in range(H)] #S beginnt am Nest, Zahlen sind die Härte des Käses, X ist das Hindernis,.Ist ein freies Grundstück
    #Ratten fressen Käse in numerischer Reihenfolge
    #Betrachten Sie BFS von jeder Nummer zur nächsten
    #Fassen Sie zuerst den Start und die Position jeder Zahl an
    start_y, start_x = 0, 0
    cheese = [(0, 0) for _ in range(10)] #Ursprünglicher Wert(0, 0)Behalten
    count = 0 #Zählen Sie die Anzahl der Käsesorten
    for row in range(H):
        for col in range(W):
            if grid[row][col] == '.' or grid[row][col] == 'X':
                continue
            elif grid[row][col] == 'S':
                start_y, start_x = row, col
            else:
                grid[row][col] = int(grid[row][col]) #Ändern Sie den Inhalt des Rasters in Zahlen
                cheese[int(grid[row][col])] = (row, col)
                count += 1
                
    # ------- [Erkunde alle Punkte] ----------
    target_cheese = 1
    time_count = 0
    while target_cheese <= count:
        time_count += bfs(start_y, start_x, target_cheese, H, W, grid)
        start_y, start_x = cheese[target_cheese]
        target_cheese += 1

    print(time_count)

Die Implementierung ist etwas schwer. Aus der Problemstellung geht hervor, dass die Maus vom Käse mit der kleineren Nummer zum Käse mit der größeren Nummer in der Reihenfolge isst. Es scheint also, dass Sie von jeder Nummer bis zur nächsten Nummer "BFS" machen sollten. Stellen Sie also `` `BFS, das eine feste Start- und Zielposition hat, in der Reihenfolge der Käsezahlen ein. s→1vonbfs、1→2vonbfs、2→3vonbfs``` ・・・と行っていき、合計von最短距離が答えとなります。

031. JOI 2012 Qualifying 5 --Illumination

Antworten

#Fügen Sie alle Nullen oben, unten, links und rechts vom Gürtel hinzu.
#Koordinate(0,0)Addieren Sie die Anzahl der Einsen, von denen aus jeder 0-Punkt erreicht werden kann

from collections import deque

# ---------- [Zählen Sie die Anzahl der Gebäude, die an Orte ohne Gebäude angrenzen] --------------
def check_walls(y, x, grid, W, H, even_moves, add_moves):
    count = 0

    if y % 2 == 0:
        moves = even_moves
    else:
        moves = add_moves
    
    for dy, dx in moves:
        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:
            continue
        if grid[moved_y][moved_x] == 1:
            count += 1
    
    return count

if __name__ == "__main__":
    # ---------- [Eingangsbeleg] --------------
    W, H = map(int, input().split())
    grid = []
    grid.append([0] * (W+2))
    for _ in range(H):
        temp = list(map(int, input().split()))
        temp = [0] + temp + [0]
        grid.append(temp)
    grid.append([0] * (W+2))
    visited = [[-1] * (W+2) for _ in range(H+2)]
    answer_count = 0
    # ---------- [Gerade und ungerade haben unterschiedliche Bewegungsrichtungen] --------------
    even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Im Uhrzeigersinn von oben links
    add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Im Uhrzeigersinn von oben links
    # ---------- [Anfangswerteinstellung] --------------
    q = deque()
    q.append((0, 0)) # (0, 0)Führen Sie BFS für Orte durch, an denen keine Gebäude erreichbar sind
    count = check_walls(0, 0, grid, W, H, even_moves, add_moves) #Zählen Sie die Anzahl der angrenzenden Gebäude
    visited[0][0] = count
    answer_count += count
    # ---------- [BFS gestartet] --------------
    while q:
        y, x = q.popleft()

        if y % 2 == 0:
            moves = even_moves
        else:
            moves = add_moves
        
        for dy, dx in moves:
            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:
                continue
            if grid[moved_y][moved_x] == 1:
                continue
            if visited[moved_y][moved_x] != -1:
                continue
            q.append((moved_y, moved_x))
            count = check_walls(moved_y, moved_x, grid, W, H, even_moves, add_moves)
            visited[moved_y][moved_x] = count
            answer_count += count

    print(answer_count)

Viele Probleme basieren auf einem Gittermuster, aber dieses Problem ist etwas anders, da ein Quadrat sechseckig ist. Die Art zu denken und zu lösen ändert sich jedoch nicht viel, und das einzige, was sich ändern muss, ist, wie die Bewegungskoordinaten von "BFS" festgelegt werden. Insbesondere ist es in meinem Fall der Teil, der durch "Bewegungen" definiert ist.

Wenn in diesem Problem die "y" -Koordinaten gerade und ungerade sind, sind die Ziele, die von jedem Quadrat verschoben werden können, unterschiedlich. Daher ist jedes wie folgt definiert.

even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Im Uhrzeigersinn von oben links
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Im Uhrzeigersinn von oben links

Wenn es sich um ein normales Gittermuster handelt, ist die Bewegungskomponente von oben / unten / links / rechts oder oben / unten / links / rechts + Diagonale wie folgt definiert, sodass nur hier anders ist.

moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Nur hoch, runter, links und rechts

moves = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)] #Rauf runter links rechts+Wenn diagonal

Wenn Sie hier gedrückt halten, wird der Rest wie folgt gelöst

1. Die große Politik besteht darin, mit "BFS" nach "Standorten ohne Gebäude" zu suchen, benachbarte Gebäude an jedem Standort zu zählen und die Summe ist die Antwort.
2. Fügen Sie zu diesem Zweck zuerst "Orte ohne Gebäude" oben, unten, links und rechts in das standardmäßig empfangene Raster ein.
3. `` `BFS``` wird von links oben (0, 0) des Gitters ausgeführt
4. Zu diesem Zeitpunkt wird nicht die übliche 0, 1 in "besucht" aufgezeichnet, sondern die Anzahl der angrenzenden Gebäude
5. Erstellen Sie daher eine Funktion `` `check_walls```, um die Anzahl benachbarter Gebäude zu zählen.
6. Seien Sie vorsichtig, wenn Sie `BFS``` ausführen, da das Verhalten davon abhängt, ob` y``` gerade oder ungerade ist.
7. Die Antwort ist die Summe der Zahlen, die von `check_walls``` zurückgegeben werden, nachdem` BFS``` durchlaufen wurde.

ist.

032. AOJ 1166 - Labyrinth und Ordnung

Antworten

from collections import deque

def main(w, h):
    tatebou = []
    yokobou = [[0] * w]
    for _ in range(h-1):
        tate = [0] + list(map(int, input().split()))
        yoko = list(map(int, input().split()))
        tatebou.append(tate)
        yokobou.append(yoko)
    tate = [0] + list(map(int, input().split()))
    tatebou.append(tate)
    visited = [[0] * w for _ in range(h)]
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    q = deque()
    q.append((0, 0))
    visited[0][0] = 1

    while q:
        y, x = q.popleft()

        for dy, dx in moves:
            moved_y = y + dy
            moved_x = x + dx

            if dy == 1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Außerhalb des Labyrinths
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[moved_y][moved_x] == 1: #Wenn Sie nach unten gehen, können Sie sich nicht bewegen, wenn das Ziel 1 ist.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == -1 and dx == 0:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Außerhalb des Labyrinths
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if yokobou[y][moved_x] == 1: #Wenn du hoch gehst, nicht wenn du 1 bist
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))

            elif dy == 0 and dx == 1:
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Außerhalb des Labyrinths
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][moved_x] == 1: #Wenn Sie nach rechts gehen, können Sie sich nicht bewegen, wenn das Ziel 1 ist.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            else: # dy == 0 and dx == -1
                if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: #Außerhalb des Labyrinths
                    continue
                if visited[moved_y][moved_x] != 0:
                    continue
                if tatebou[moved_y][x] == 1: #Wenn Sie nach links gehen, können Sie nicht, wenn Sie 1 sind.
                    continue
                visited[moved_y][moved_x] = visited[y][x] + 1
                q.append((moved_y, moved_x))
            
    return visited[h-1][w-1]


if __name__ == "__main__":

    answer_list = []
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break

        answer = main(w, h)
        answer_list.append(answer)

    for answer in answer_list:
        print(answer)

Im Grunde ist es dasselbe wie Problem 29. Der Unterschied ist das Trefferurteil. Problem 29 ist einfach, weil es ein Trefferurteil war, dass "man nicht zur Masse selbst gehen kann", aber dieses Problem ist nicht "Masse", sondern "Wand". Daher ist es notwendig, Fälle zu trennen, die für ein normales "BFS" nicht erforderlich sind. Insbesondere ist es erforderlich, das Trefferurteil wie unten gezeigt zu ändern, je nachdem, wie Sie sich nach oben, unten, links und rechts bewegen.

            if dy == 1 and dx == 0:
                if yokobou[moved_y][moved_x] == 1: #Wenn Sie nach unten gehen, können Sie sich nicht bewegen, wenn das Ziel 1 ist.
                    continue
            elif dy == -1 and dx == 0:
                if yokobou[y][moved_x] == 1: #Wenn du hoch gehst, nicht wenn du 1 bist
                    continue
            elif dy == 0 and dx == 1:
                if tatebou[moved_y][moved_x] == 1: #Wenn Sie nach rechts gehen, können Sie sich nicht bewegen, wenn das Ziel 1 ist.
                    continue
            else: # dy == 0 and dx == -1
                if tatebou[moved_y][x] == 1: #Wenn Sie nach links gehen, können Sie nicht, wenn Sie 1 sind.
                    continue

Abgesehen von diesem Trefferurteil schreiben Sie einfach normal.

33. AtCoder Beginner Contest 088 D - Grid Repainting

Antworten

#Nur Weiß bewegt sich(0,0)Von(H-1, W-1)gehe zu
#Erhöhen Sie zu diesem Zeitpunkt das Schwarz so weit wie möglich
#Die Antwort ist das gesamte Weiß abzüglich der kürzesten Entfernung

from collections import deque


H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .Ist weiß,#Ist schwarz
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]

q = deque()
q.append((0, 0))
visited[0][0] = 0

while q:
    y, x = q.popleft()

    for dy, dx in moves:
        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:
            continue
        if grid[moved_y][moved_x] == '#':
            continue
        if visited[moved_y][moved_x] != -1:
            continue

        visited[moved_y][moved_x] = visited[y][x] + 1
        q.append((moved_y, moved_x))

min_route = visited[H-1][W-1]

if min_route == -1:
    answer = -1
else:
    total_white = 0
    for row in grid:
        total_white += row.count('.')

    answer = total_white - min_route - 1

print(answer)

Dies ist ziemlich einfach, wenn Sie andere Probleme lösen können. Wenn Sie das Problem kauen und interpretieren, lautet die Antwort "die Anzahl der schwarzen Farben beim Übergang von links oben nach rechts unten". Wenn Sie dies etwas einfacher interpretieren, ist es "die Anzahl der anderen Stellen, die nicht passieren, wenn Sie sich auf kürzestem Weg von links oben nach rechts unten bewegen". Sobald Sie dies wissen, können Sie normalerweise die kürzeste Entfernung mit `` `BFS``` berechnen und vom Ganzen subtrahieren.

So ist die Politik

1. `(0,0)` Start, `(H-1, W-1)` `Ziel zur Berechnung der kürzesten Distanz` min_route```
2. Berechnen Sie die Gesamtzahl der Weißen `total_white `
3. Die Antwort lautet `total_white minus min_route``` ( min_route``` ist ein Nullstart, also addiere -1)

ist.