Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
1. Objet
Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.
Cet article s'intitule "Recherche de priorité de largeur 028 --033".
2. Résumé
dfsSi possiblebfsEst presque le même.
La différence est que `deque ()` apparaît depuis `pop ()` ʻin` `DFS``` et` popleft () dans`` BFS```. Utilisez ``.
3. Histoire principale
028 --033 Recherche de priorité de largeur
028. ALDS_11_C --Width priority search
Répondre
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
i, num, *nodes = map(int, input().split()) # *Collecter plus
graph[i] = nodes #Graphique dirigé
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)
C'est un problème fondamental. Si vous créez votre propre moule ici, vous pourrez résoudre d'autres problèmes avec juste quelques ajustements.
bfsSi vous montrez approximativement le flux de
- Utilisez ``
visité ''`pour créer une liste de destinations de recherche. - Préparez `` deque () '' pour le moment et entrez la valeur initiale
- Tourner
`while``` jusqu'à ce que`deque () `` `soit vide - Utilisez
- Examinez le ``
graphe'' des valeurs récupérées pour trouver la destination - Déterminez si la destination a été recherchée
- Mettez à jour
appendet `` `visité``` si vous ne recherchez pas
est.
029. AtCoder Beginner Contest 007 C --Width priority search
Répondre
from collections import deque
R, C = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1 #Fixé à 0 index
sx -= 1
gy, gx = map(int, input().split())
gy -= 1 #Fixé à 0 index
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])
Ceci est typique du typique. Je m'en souviendrai pour le moment.
030. JOI 2011 Qualifying 5-Cheese
Répondre
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 commence au nid, les nombres sont la dureté du fromage, X est l'obstacle,.Est un terrain vague
#Les rats mangent du fromage dans l'ordre numérique
#Considérez BFS de chaque nombre au suivant
#Saisissez d'abord le début et la position de chaque numéro
start_y, start_x = 0, 0
cheese = [(0, 0) for _ in range(10)] #Valeur initiale(0, 0)Garder
count = 0 #Mettre le nombre de fromages en compte
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]) #Changer le contenu de la grille en nombres
cheese[int(grid[row][col])] = (row, col)
count += 1
# ------- [Explorer tous les points] ----------
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)
La mise en œuvre est un peu lourde.
À partir de l'énoncé du problème, la souris mange du fromage avec le plus petit nombre au fromage avec le plus grand nombre dans l'ordre, il semble donc que vous devriez faire BFS '' de chaque numéro au numéro suivant. Alors, définissez BFS '', qui a une position de départ et une position de but fixes, dans l'ordre des numéros de fromage.
s→1debfs、1→2debfs、2→3debfs ・・・と行っていき、合計de最短距離が答えとなります。
031. JOI 2012 Qualifying 5 --Illumination
Répondre
#Ajoutez tous les 0 en haut, en bas, à gauche et à droite de la ceinture,
#Coordonner(0,0)Additionnez le nombre de 1 d'où chaque point 0 qui peut être atteint
from collections import deque
# ---------- [Comptez le nombre de bâtiments adjacents à des endroits sans bâtiments] --------------
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__":
# ---------- [Reçu d'entrée] --------------
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
# ---------- [Pair et impair ont des directions de mouvement différentes] --------------
even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Dans le sens des aiguilles d'une montre à partir du coin supérieur gauche
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Dans le sens des aiguilles d'une montre à partir du coin supérieur gauche
# ---------- [Réglage de la valeur initiale] --------------
q = deque()
q.append((0, 0)) # (0, 0)Effectuer des BFS pour les endroits où il n'y a pas de bâtiments accessibles depuis
count = check_walls(0, 0, grid, W, H, even_moves, add_moves) #Comptez le nombre de bâtiments adjacents
visited[0][0] = count
answer_count += count
# ---------- [BFS a commencé] --------------
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)
De nombreux problèmes sont basés sur un modèle de grille, mais ce problème est légèrement différent car un carré est hexagonal.
Cependant, la façon de penser et de résoudre ne change pas beaucoup, et la seule chose à changer est de savoir comment définir les coordonnées de mouvement de BFS ''. Plus précisément, dans mon cas, c'est la partie définie par se déplace ''.
Dans ce problème, lorsque les coordonnées `` y '' sont paires et impaires, les destinations qui peuvent être déplacées de chaque carré sont différentes. Par conséquent, chacun est défini comme suit.
even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] #Dans le sens des aiguilles d'une montre à partir du coin supérieur gauche
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] #Dans le sens des aiguilles d'une montre à partir du coin supérieur gauche
S'il s'agit d'un modèle de grille normal, la composante de mouvement haut / bas / gauche / droite ou haut / bas / gauche / droite + diagonale est définie comme suit, donc seulement ici est différente.
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Seulement en haut, en bas, à gauche et à droite
moves = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)] #Haut bas Gauche Droite+Lorsque la diagonale
Si vous maintenez ici, le reste sera résolu comme la politique suivante
- La grande politique est de rechercher des «emplacements sans bâtiments» avec «BFS», de compter les bâtiments adjacents à chaque emplacement, et le total est la réponse.
- Pour cela, ajoutez d'abord des "lieux sans bâtiments" en haut, en bas, à gauche et à droite de la grille reçue par défaut.
- À ce moment-là, ce n'est pas le 0, 1 habituel qui est enregistré dans `` visité '', mais le nombre de bâtiments adjacents
- Par conséquent, créez une fonction `` check_walls '' pour compter le nombre de bâtiments adjacents.
- Lors de l'exécution de
BFS, soyez prudent car le comportement diffère selon que `` y``` est pair ou impair. - La réponse est la somme des nombres renvoyés par
`check_walls``` après avoir traversé`BFS```.
est.
032. AOJ 1166 - Labyrinthe et ordre
Répondre
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: #En dehors du labyrinthe
continue
if visited[moved_y][moved_x] != 0:
continue
if yokobou[moved_y][moved_x] == 1: #Lorsque vous descendez, vous ne pouvez pas vous déplacer lorsque la destination est 1.
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: #En dehors du labyrinthe
continue
if visited[moved_y][moved_x] != 0:
continue
if yokobou[y][moved_x] == 1: #Quand tu montes, pas quand tu as 1
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: #En dehors du labyrinthe
continue
if visited[moved_y][moved_x] != 0:
continue
if tatebou[moved_y][moved_x] == 1: #Lorsque vous allez vers la droite, vous ne pouvez pas vous déplacer lorsque la destination est 1.
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: #En dehors du labyrinthe
continue
if visited[moved_y][moved_x] != 0:
continue
if tatebou[moved_y][x] == 1: #Lorsque vous allez à gauche, vous ne pouvez pas quand vous êtes 1.
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)
Fondamentalement, c'est la même chose que le problème 29. La différence est le jugement de succès. Le problème 29 est facile parce que c'était un jugement frappant que "vous ne pouvez pas aller à la masse elle-même", mais ce problème n'est pas "masse" mais "mur". Par conséquent, il est nécessaire de séparer les cas qui ne sont pas nécessaires pour un `` BFS '' normal. Plus précisément, il est nécessaire de modifier le jugement de frappe comme indiqué ci-dessous en fonction de la façon dont vous vous déplacez vers le haut, le bas, la gauche et la droite.
if dy == 1 and dx == 0:
if yokobou[moved_y][moved_x] == 1: #Lorsque vous descendez, vous ne pouvez pas vous déplacer lorsque la destination est 1.
continue
elif dy == -1 and dx == 0:
if yokobou[y][moved_x] == 1: #Quand tu montes, pas quand tu as 1
continue
elif dy == 0 and dx == 1:
if tatebou[moved_y][moved_x] == 1: #Lorsque vous allez vers la droite, vous ne pouvez pas vous déplacer lorsque la destination est 1.
continue
else: # dy == 0 and dx == -1
if tatebou[moved_y][x] == 1: #Lorsque vous allez à gauche, vous ne pouvez pas quand vous êtes 1.
continue
À part ce jugement frappé, écrivez simplement normalement.
Répondre
#Seuls les blancs bougent(0,0)De(H-1, W-1)aller à
#À ce moment-là, augmentez le noir autant que possible
#La réponse est le blanc total moins la distance la plus courte
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .Est blanc,#Est noir
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)
C'est assez facile si vous pouvez résoudre d'autres problèmes. Si vous mâchez le problème et l'interprétez, la réponse est "le nombre de peintures noires lors du déplacement du coin supérieur gauche vers le coin inférieur droit". Pour rendre cela plus facile à résoudre, c'est "le nombre d'autres endroits qui ne passent pas lors du déplacement du haut à gauche vers le bas à droite par la distance la plus courte". Une fois que vous savez cela, vous pouvez généralement calculer la distance la plus courte avec `` BFS '' et la soustraire du tout.
Donc, la politique est
`(0,0)`start,- Calculez le nombre total de blancs
`total_white` - La réponse est
`total_whitemoinsmin_route``` (min_route``` est un départ nul, donc ajoutez -1)
est.
Recommended Posts