[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 7/22]

** Visez un codeur bleu clair! !! !! !! !! !! ** **

Alors [Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue 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 a rassemblé 100 bonnes questions éducatives qui conviennent aux codeurs marron et vert afin d'obtenir un codeur bleu clair, ou une note de 1200, avec un petit nombre de questions.

100 questions passées que les débutants et les intermédiaires devraient résoudre dans cet article` Sera résolu avec ** Python **! Merci à @ e869120! !! !! !! !! !!

Lien vers l'article précédent

** Rechercher tout: Tout lister ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part1 / 22] ** Recherche complète: toute énumération pour réduire le nombre de rues en concevant ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part2 / 22] ** Recherche complète: recherche complète de bits ** [[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Recherche complète: avant la recherche complète ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part4 / 22] ** Recherche par section ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part5 / 22] ** Recherche de priorité de profondeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part6 / 22] ** Recherche de priorité de largeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part7 / 22]

"Partie 7" ~ Edition de recherche de priorité de largeur (BFS) ~

Nous allons résoudre les 6 questions suivantes!

Recherche de priorité de largeur

28 ALDS_11_C --Width priority search C'est un problème de base. 29 AtCoder Beginner Contest 007 C - Recherche avec priorité à la largeur Le problème de l'itinéraire le plus court des graphiques non pondérés peut être résolu par une recherche avec priorité à la largeur. 30 5 fromages de qualification JOI 2011 31 JOI 2012 Qualifying 5-Illumination La mise en œuvre est un peu lourde, mais si vous faites de votre mieux, vous pouvez la résoudre. 32 AOJ 1166 - L'implémentation est un peu lourde. 33 Concours AtCoder Débutant 088 D - Repeindre la grille Si cela est résolu, vous pouvez penser que vous êtes habitué à la recherche de priorité de largeur.

Prérequis BFS

・ J'écrirai un article basé sur les deux points suivants! ** ① Vous avez une certaine compréhension de DFS ** La méthode d'implémentation BFS est presque la même que la méthode d'implémentation DFS! (Utilisez simplement la file d'attente au lieu de la pile!) Tout d'abord, comprenons DFS!

** Recherche de priorité de profondeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part6 / 22]

② À propos de BFS L'article de Kenchon BFS (Width Priority Search) Super Introduction! ~ Utilisez la file d'attente de façon vivante ~ En savoir plus sur BFS ** Comprenez l'ambiance! ** **

(Pas de poids) BFS est également utile pour le problème d'itinéraire le plus court dans les graphiques! !! !!

Si vous avez la prémisse de ①②, vous pouvez l'apprendre en bougeant réellement vos mains! !! !!

28 ALDS_11_C --Width priority search

Comment implémenter BFS est le même que DFS ** La femme de ménage a vu! Il suffit de mettre (vu) et de "cue" ** est! (Pour ceux qui ne comprennent pas ce qu'ils disent, voir Articles précédents!)

BFS était une pile, mais DFS était en file d'attente, Lors du retrait de la file d'attente, c'est popleft ()!

Créons min_dist comme variable ~ ** C'était étonnamment facile à mettre en œuvre! !! !! ** **

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() #Mettez le sommet NON
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 C'est un problème typique de l'itinéraire le plus court! C'est presque la même chose que le problème du bluff de grille DFS ~ J'ai pu implémenter ce problème même **! ** **

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[ligne,Colonne]Mettre en
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

Encore une fois, le problème est un peu plus compliqué, mais l'idée est exactement la même que le problème précédent ~ Ce problème a également été résolu ** sans difficulté ~ **

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[ligne,Colonne]Mettre en
    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

** Je n'ai pas pu le résoudre à première vue! !! !! ** ** Je ne pouvais pas considérer cela comme une peinture de l'extérieur de la carte! Jusqu'à présent, le problème du quadrillage n'était que dans les quatre directions gauche, droite, haut et bas, Le problème cette fois est un hexagone, il y a donc 6 directions! En regardant l'explication, vous pouvez certainement penser à la même idée que dans 4 directions, et vous pouvez la considérer comme une surface murale qui heurte un mur!

De plus, même si j'ai essayé de l'implémenter après avoir vu l'explication, la réponse ne correspondait pas à l'exemple d'entrée / sortie ... La cause était que j'avais besoin d'une marge de deux lignes au-dessus et en dessous (lignes paires) au lieu d'une marge d'une ligne au-dessus et en dessous! ** ** (Les lignes paires et impaires sont incohérentes ...)

C'était difficile, mais c'était un bon problème! !! !! J'ai beaucoup appris! !! !!

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[ligne,Colonne]Mettre en
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 - Labyrinthe et ordre

** Je n'ai pas pu résoudre ça à première vue non plus! !! !! ** **

J'ai fait de mon mieux en préparant un cahier et un stylo, mais c'était dur! J'ai abandonné et j'ai vu le code de quelqu'un qui peut! Premier, ** S'il est vers le haut ou vers le bas ** Il ne bouge pas latéralement, vous pouvez donc ignorer le mur vertical! ** ** (De même pour la gauche et la droite, ** vous pouvez ignorer les parois latérales! **) plus tard, Les conditions pour vérifier s'il y a un mur sont différentes entre le haut et la gauche et le bas et la droite! ** ** ** À l'heure ci-dessus, vérifiez s'il existe un mur avec l'index de nh **, mais ** En bas, vérifiez s'il y a un mur avec l'index de nh-1 (lieu d'origine!) **! (De même à gauche et à droite, ** à droite, vérifiez s'il y a un mur avec l'index de nw-1 (emplacement d'origine!) **!)

a été difficile!

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[ligne,Colonne]Mettre en
    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)

Supplément

print(bfs() or 0)

Ce ʻou renverra 0 si la valeur de retour est None! (Autrement dit, return min_dist [qh] [qw] + 1` n'est pas revenu! = Renvoie 0 si vous ne pouvez pas atteindre le coin inférieur droit! )

Au fait, cela n'a rien à voir avec BFS ** Je suis resté coincé dans un endroit où cela n'a pas d'importance ** Pendant le débogage, le code est censé être correct, mais il boucle indéfiniment ... La cause est Le dernier vu [nh] [nw] = 1 C'était vu [nh] [nw] == 1 et == ... Cela ne peut pas être aidé, mais j'ai tué beaucoup de temps pour trouver cette cause. (Quand j'ai suspecté que la condition de la déclaration if était mal écrite, le temps passait.)

Le code est long, donc lorsqu'un bug survient, il faut du temps pour découvrir ce qui l'a causé! Mais le problème difficile sera plus de code, ** Ne vous découragez pas dans un endroit comme celui-ci! !! !! ** **

33　AtCoder Beginner Contest 088 D - Grid Repainting Difficulty:997 ** Cela a trouvé une solution! ** ** Il ne vous reste plus qu'à l'implémenter!

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[ligne,Colonne]Mettre en
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)

La prochaine fois, je résoudrai les 12 questions suivantes!

Planification dynamique: Knapsack DP 34 ALDS_10_A - Numéro Fibonatch super basique. Vous pouvez ressentir "qu'est-ce que DP". 35 DPL_1_B --0,1 Problème de sac à dos C'est un problème de base. 36 DPL_1_C --Problème de Knapsack Il s'agit d'un problème de base. 37 DPL_1_A --Problème de pièce de monnaie C'est un problème de base. 38 ALDS_10_C --La sous-colonne commune la plus longue est un problème de base.

(À partir de là, je n'écrirai pas quel type de DP peut être résolu, mais tout peut être résolu avec Knapsack DP ou ses variantes.)

39 JOI 2011 Qualifying 4-1st grade 40 4-pâtes qualificatives JOI 2012 41 JOI 2013 Qualifying 4-Hot days 42 JOI 2015 Qualifications 4-Route de la Soie 43 Pa Lab Cup 2019 D - Pavillon Pa Lab 44 AOJ 1167 - Prévisions de Polock 45 AOJ 2199 - Modulation du code d'impulsion de différence

Part7/22 fin!

Suivant (Partie 8/22)