[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 7/22]

** Streben Sie einen hellblauen Codierer an! !! !! !! !! !! ** ** **

Damit [Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)

AtCoder hat 100 gute pädagogische Fragen gesammelt, die für braune und grüne Codierer geeignet sind, um mit einer kleinen Anzahl von Fragen einen hellblauen Codierer oder eine Bewertung von 1200 zu erreichen.

Die 100 früheren Fragen dieses Artikels, die Anfänger und Fortgeschrittene lösen sollten Wird mit ** Python ** gelöst! Vielen Dank an @ e869120! !! !! !! !! !!

Link zum letzten Artikel

** Alle durchsuchen: Alle auflisten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22] ** Vollständige Suche: Alle Aufzählungen zur Reduzierung der Anzahl der Straßen durch Ausarbeitung ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] ** Vollständige Suche: Bit vollständige Suche ** [[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Vollständige Suche: Vollständige Suche weiterleiten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part4 / 22] ** Halbierungssuche ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part5 / 22] ** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22] ** Suche nach Breitenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part7 / 22]

"Teil 7" ~ BFS-Edition (Width Priority Search) ~

Wir werden die folgenden 6 Fragen lösen!

Suche nach Breitenpriorität

28 ALDS_11_C - Breite Prioritätssuche Dies ist ein grundlegendes Problem. 29 AtCoder-Anfängerwettbewerb 007 C - Suche nach Breite mit Priorität Das Problem der kürzesten Route bei ungewichteten Diagrammen kann durch Suche nach Breite und Priorität gelöst werden. 30 JOI 2011 Qualifying 5-Cheese 31 JOI 2012 Qualifying 5-Illumination Die Implementierung ist etwas schwer, aber wenn Sie Ihr Bestes geben, können Sie sie lösen. 32 AOJ 1166 - Die Implementierung ist etwas schwer. 33 AtCoder Anfängerwettbewerb 088 D --Grid Repainting Wenn dies behoben ist, können Sie denken, dass Sie an die Suche nach Breitenprioritäten gewöhnt sind.

BFS-Voraussetzungen

・ Ich werde einen Artikel schreiben, der auf den folgenden zwei Punkten basiert! ** ① Sie haben ein gewisses Verständnis von DFS ** Die BFS-Implementierungsmethode ist fast dieselbe wie die DFS-Implementierungsmethode! (Verwenden Sie einfach die Warteschlange anstelle des Stapels!) Lassen Sie uns zuerst DFS verstehen!

** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22]

② Über BFS Kenchons Artikel BFS (Width Priority Search) Super Einführung! ~ Verwenden Sie die Warteschlange lebhaft ~ Lesen Sie mehr über BFS ** Verstehen Sie die Atmosphäre! ** ** **

(Kein Gewicht) BFS ist auch nützlich für das Problem der kürzesten Route in Grafiken! !! !!

Wenn Sie die Prämisse von ①② haben, können Sie es lernen, indem Sie tatsächlich Ihre Hände bewegen! !! !!

28 ALDS_11_C - Suche mit breiter Priorität

Die Implementierung von BFS entspricht der von DFS ** Die Haushälterin sah! Einfach setzen (gesehen) und "Stichwort" ** ist! (Für diejenigen, die nicht verstehen, was sie sagen, siehe Frühere Artikel!)

BFS war ein Stapel, aber DFS wurde in die Warteschlange gestellt, Beim Entfernen aus der Warteschlange ist es "popleft ()"!

Lassen Sie uns min_dist als Variable ~ erstellen ** Es war unerwartet einfach zu implementieren! !! !! ** ** **

test.py

import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
min_dist = [-1]*(n+1) #1_indexed
queue = collections.deque() #Setzen Sie den Scheitelpunkt NO
def bfs():
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not graph[q_NO]:
            continue
        g = graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for i,ans in enumerate(min_dist[1:],1):
    print(i,ans)

29　AtCoder Beginner Contest 007 C Difficulty:1003 Es ist ein typisches Problem mit der kürzesten Route! Es ist fast das gleiche wie das DFS-Grid-Bluff-Problem ~ Ich konnte dieses Problem sogar umsetzen **! ** ** **

test.py

import collections,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
R,C = LI()
sy,sx = [i-1 for i in LI()]
gy,gx = [i-1 for i in LI()]
c = [S() for _ in range(R)]
drdc = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*C for _ in range(R)]
seen = [[0]*C for _ in range(R)]
queue = collections.deque() #Position[Linie,Säule]Einstellen
def bfs():
    seen[sy][sx] = 1
    queue.append([sy,sx])
    min_dist[sy][sx] = 0
    while queue:
        qr,qc = queue.popleft()
        for dr,dc in drdc:
            nr,nc = qr+dr,qc+dc
            if c[nr][nc]=='#' or seen[nr][nc]:
                continue
            if [nr,nc]==[gy,gx]:
                return min_dist[qr][qc]+1
            seen[nr][nc] = 1
            queue.append([nr,nc])
            min_dist[nr][nc] = min_dist[qr][qc]+1
print(bfs())

30 JOI 2011 Qualifying 5-Cheese

Auch hier ist das Problem etwas komplizierter, aber die Idee ist genau die gleiche wie beim vorherigen Problem ~ Dieses Problem wurde auch ** ohne Schwierigkeiten ~ ** gelöst

test.py

import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W,N = LI()
area = [S() for _ in range(H)]
ans = 0
S_factory_point = [[-1,-1] for _ in range(N+1)] #1_indexed
for h,w in itertools.product(range(H),range(W)):
    if area[h][w]=='S':
        S_factory_point[0] = [h,w]
    if area[h][w] in list(map(str,list(range(1,N+1)))):
        S_factory_point[int(area[h][w])] = [h,w]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
def bfs(sh,sw,target_factory_NO):
    min_dist = [[-1]*W for _ in range(H)]
    seen = [[0]*W for _ in range(H)]
    queue = collections.deque() #Position[Linie,Säule]Einstellen
    seen[sh][sw] = 1
    queue.append([sh,sw])
    min_dist[sh][sw] = 0
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or area[nh][nw]=='X':
                continue
            if [nh,nw]==S_factory_point[target_factory_NO]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
for i in range(N):
    sh,sw = S_factory_point[i]
    ans += bfs(sh,sw,i+1)
print(ans)

31 JOI 2012 Qualifying 5-Illumination

** Ich konnte es auf den ersten Blick nicht lösen! !! !! ** ** ** Ich konnte mir das nicht als Malerei von außerhalb der Karte vorstellen! Bisher bestand das Problem des Gittergraphen nur in den vier Richtungen links, rechts, oben und unten. Das Problem ist diesmal ein Sechseck, es gibt also 6 Richtungen! Wenn Sie sich die Erklärung ansehen, können Sie sich sicherlich die gleiche Idee wie in den vier Richtungen vorstellen, und Sie können sich eine Wandoberfläche vorstellen, die gegen eine Wand stößt!

Auch wenn ich versucht habe, es zu implementieren, nachdem ich die Erklärung gesehen habe, stimmte die Antwort nicht mit dem Eingabe- / Ausgabebeispiel überein ... Die Ursache war, dass ich einen Rand von zwei Zeilen über und unter (gerade Linien) anstelle eines Randes von einer Zeile über und unter brauchte! ** ** ** (Ungerade und gerade Linien sind inkonsistent ...)

Es war schwierig, aber es war ein gutes Problem! !! !! Ich habe viel gelernt! !! !!

test.py

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
W,H = LI()
sub_area = [[0]+LI()+[0] for _ in range(H)]
area = [[0]*(W+2)]+[[0]*(W+2)]+sub_area+[[0]*(W+2)]+[[0]*(W+2)]
dhdw_even = [[-1,0],[-1,1],[0,-1],[0,1],[1,0],[1,1]]
dhdw_odd = [[-1,-1],[-1,0],[0,-1],[0,1],[1,-1],[1,0]]
seen = [[0]*(W+2) for _ in range(H+4)]
queue = collections.deque() #Position[Linie,Säule]Einstellen
def bfs():
    ans = 0
    seen[0][0] = 1
    queue.append([0,0])
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw_even if qh%2==0 else dhdw_odd:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=(H+4)-1) or not(0<=nw<=(W+2)-1) or seen[nh][nw]:
                continue
            if area[nh][nw]==1:
                ans += 1
                continue
            seen[nh][nw] = 1
            queue.append([nh,nw])
    return ans
print(bfs())

32 AOJ 1166 - Labyrinth und Ordnung

** Ich konnte das auch nicht auf den ersten Blick lösen! !! !! ** ** **

Ich habe mein Bestes gegeben, als ich ein Notizbuch und einen Stift vorbereitet habe, aber es war schwer! Ich gab auf und sah den Code von jemandem, der kann! Zuerst, ** Wenn es nach oben oder unten geht ** Es bewegt sich nicht seitwärts, sodass Sie die vertikale Wand ignorieren können! ** ** ** (Ebenso für links und rechts ** können Sie die Seitenwände ignorieren! **) später, Die Bedingungen für die Überprüfung, ob eine Wand vorhanden ist, unterscheiden sich zwischen oben und links sowie unten und rechts! ** ** ** ** Überprüfen Sie zum obigen Zeitpunkt, ob es eine Wand mit dem Index nh ** gibt, aber ** Überprüfen Sie unten, ob es eine Wand mit dem Index "nh-1" gibt (ursprünglicher Ort!) **! (Überprüfen Sie links und rechts, ** rechts, ob es eine Wand mit dem Index "nw-1" gibt (ursprüngliche Position!) **!)

war schwierig!

test.py

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
    w,h = LI()
    if w==h==0:
        break
    hwall,wwall = [],[]
    for i in range(2*h-1):
        hwall.append(LI()) if i%2==0 else wwall.append(LI())
    dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
    min_dist = [[-1]*w for _ in range(h)]
    seen = [[0]*w for _ in range(h)]
    queue = collections.deque() #Position[Linie,Säule]Einstellen
    def bfs():
        seen[0][0] = 1
        queue.append([0,0])
        min_dist[0][0] = 1
        while queue:
            qh,qw = queue.popleft()
            for dh,dw in dhdw:
                nh,nw = qh+dh,qw+dw
                if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw]:
                    continue
                if (dh==-1 and wwall[nh][nw]==1) or (dh==1 and wwall[nh-1][nw]==1):
                    continue
                if (dw==-1 and hwall[nh][nw]==1) or (dw==1 and hwall[nh][nw-1]==1):
                    continue
                if [nh,nw]==[h-1,w-1]:
                    return min_dist[qh][qw]+1
                seen[nh][nw] = 1
                queue.append([nh,nw])
                min_dist[nh][nw] = min_dist[qh][qw]+1
    print(bfs() or 0)

Ergänzung

print(bfs() or 0)

Dieses oder gibt 0 zurück, wenn der Rückgabewert None ist! (Das heißt, return min_dist [qh] [qw] + 1 ist nicht zurückgekommen! = Gibt 0 zurück, wenn Sie unten rechts nicht erreichen können! )

Übrigens hat es nichts mit BFS zu tun ** Ich steckte an einem Ort fest, an dem es keine Rolle spielt ** Während des Debuggens soll der Code korrekt sein, aber er wird auf unbestimmte Zeit wiederholt ... Die Ursache ist Das letzte "gesehen [nh] [nw] = 1" Es wurde "gesehen [nh] [nw] == 1" und "==" ... Es kann nicht geholfen werden, aber ich habe viel Zeit getötet, um diese Ursache zu finden. (Als ich vermutete, dass die Bedingung der if-Anweisung falsch geschrieben war, verging die Zeit.)

Der Code ist lang. Wenn also ein Fehler auftritt, dauert es einige Zeit, um herauszufinden, was ihn verursacht hat! Aber das schwierige Problem wird mehr Code sein, ** Lassen Sie sich an einem Ort wie diesem nicht entmutigen! !! !! ** ** **

33　AtCoder Beginner Contest 088 D - Grid Repainting Difficulty:997 ** Dies kam mit einer Lösung! ** ** ** Alles was Sie tun müssen, ist es zu implementieren!

test.py

import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='#':
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #Position[Linie,Säule]Einstellen
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
                continue
            if [nh,nw]==[H-1,W-1]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
    else:
        return -1
min_dist = bfs()
print(H*W-black_count-min_dist if min_dist!=-1 else -1)

Nächstes Mal werde ich die folgenden 12 Fragen lösen!

Dynamische Planung: Knapsack DP 34 ALDS_10_A - Fibonatch-Nummer super basic. Sie können fühlen, "was ist DP". 35 DPL_1_B --0,1 Rucksackproblem Dies ist ein Grundproblem. 36 DPL_1_C --Knapsack-Problem Dies ist ein grundlegendes Problem. 37 DPL_1_A - Münzproblem Dies ist ein Grundproblem. 38 ALDS_10_C - Die längste gemeinsame Unterspalte ist ein Grundproblem.

(Von hier an werde ich nicht mehr schreiben, welche Art von DP gelöst werden kann, aber alle können mit Knapsack DP oder seinen Varianten gelöst werden.)

39 JOI 2011 Qualifikation 4-1. Klasse 40 JOI 2012 Qualifying 4-Pasta 41 JOI 2013 Qualifying 4-Hot Days 42 JOI 2015 Qualifying 4-Silk Road 43 Pa Lab Cup 2019 D - Pa Lab Flagge 44 AOJ 1167 - Polock-Prognose 45 AOJ 2199 - Differenzpulscodemodulation

Part7/22 Ende!

Weiter (Teil 8/22)