Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (024 --027 Recherche de priorité en profondeur)
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 "024-027 Recherche prioritaire en profondeur".
2. Résumé
C'est facile à écrire dans l'article ci-dessous, mais il m'a fallu beaucoup de temps pour comprendre BFS '' et DFS ''.
bfsQuanddfsの基本形をおさえるまでに、最初は解説を読んでもまったくわからず、理解するまでに1週間くらい（1日10時間以上悩むこQuandもあった）かかっています。
Bien sûr, j'ai lu l'article de commentaire pour comprendre, mais j'ai essayé de déboguer le code qui passe par `` AC '' et de voir comment les données fonctionnent ligne par ligne. Je l'ai fait jusqu'à ce que je comprenne que je le confirmerais. Quant à la récurrence, j'ai en fait écrit tous les calculs récursifs dans une note.
Puis, à un moment donné, les structures de données de BFS '' et DFS '' ont été créées dans ma tête, et même si je n'ai rien écrit dans le cahier, j'ai pensé Il était possible de déplacer des données comme BFS '', DFS ''.
Peut-être que ce moment viendra en fonction de l'individu, mais je pense qu'il ne viendra pas sans un certain temps de réflexion (épreuve?).
De plus, le débogage utilise le développeur du code VS. Pratique. Comme ça.
3. Histoire principale
024 --027 Recherche de priorité de profondeur
024. ALDS_11_B - Recherche par priorité en profondeur
Répondre
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N):
i, num, *nodes = map(int, input().split())
graph[i] = nodes #Graphique dirigé
go_time = [0] * (N+1)
back_time = [0] * (N+1)
def dfs(node, t):
#Record d'aller
t += 1
go_time[node] = t
for next_node in graph[node]:
if go_time[next_node] == 0:
t = dfs(next_node, t)
#Dossier de retour
t += 1
back_time[node] = t
return t
t = 0
for node in range(1, N+1): #Essayez de partir de tous les points
if go_time[node] == 0:
t = dfs(node, t)
print(node, go_time[node], back_time[node])
Tout d'abord, recevoir des données est gênant.
En ce qui concerne la façon de recevoir les informations du graphique, l'endroit où la longueur est variable est le dernier comme ```i, num, * nodes = map (int, input (). Split ()) ` Vous pouvez passer le reste aux nœuds``` en ajoutant * '' aux * nœuds``. Référence-> Décompresser les taples et les listes en Python (développer et assigner à plusieurs variables)
Comme vous pouvez le voir en soumettant ici, il peut y avoir certaines parties que vous ne pouvez pas atteindre même si vous partez de 1 (je ne sais pas où vous pouvez lire cela dans l'énoncé du problème ...), alors essayez tous les points en tant que candidats pour commencer est nécessaire.
Les deux dfs par récursif écrit cette fois et `` `` dfs par `` deque``` (dans le cas de python) doivent d'abord se souvenir du type de base, et de l'explication du type de base C'est assez difficile pour moi, alors je vais l'omettre.
Pour le moment, je vais apprendre cette forme de base et procéder dans un premier temps.
025. AOJ 1160 - Combien d'îles y a-t-il?
Répondre
from collections import deque
def main(w, h, MAP, visited):
count = 0
#Essayez de partir de tous les points
for start_y in range(h):
for start_x in range(w):
if MAP[start_y][start_x] == 0: #Passer dans le cas de la mer
continue
if visited[start_y][start_x] != -1: #Passer la recherche
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: #Évitez de quitter la carte
continue
if MAP[moved_y][moved_x] == 0: #Passer dans le cas de la mer
continue
if visited[moved_y][moved_x] != -1: #Passer la recherche
continue
visited[moved_y][moved_x] = 1
q.append((moved_y, moved_x))
count += 1 #Une île après avoir traversé pendant
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)
Personnellement, il est plus facile d'écrire dfs '' par deck (decue?) Que récursif. C'est aussi la forme de base de dfs '' (je pense), alors écrivez-la telle quelle.
Répondre
from collections import deque
# -------------- [contribution] --------------
N, Q = map(int, input().split()) #N est le nombre de sommets, Q est le nombre d'opérations
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)
# -------------- [À partir de 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] #Ajouter un score parental
print(*counts[1:])
Ce problème est AtCoder Beginner Contest 176 D --Wizard in Maze (Cliquez ici pour mon article de réponse → AtCoder ABC 176 Python (A ~ E) )) J'ai senti que c'était un peu comme ça. Ce problème est plus simple, mais ...
Ce qui est similaire est compte [suivant] + = compte [nœud] '' dans cette partie, visité [déplacé_y] [déplacé_x] = visité [dans ABC 176] y] [x] `` Ici.
La raison pour laquelle je pensais que c'était similaire est lors du déplacement de la cible de recherche (appelons-la ①) extraite par q.pop () '' `` à la cible de recherche (appelons-la ②) à côté de la cible de recherche ①. Ceci est dû au fait que le processus de mise à jour des informations dans (2) à l'aide des informations de (1) est similaire.
En normal (?) DFS``` et BFS, je pense que la mise à jour des informations dans ② ci-dessus est souvent une autre liste ou juste un incrément, mais la même liste J'ai pensé qu'il serait difficile de trouver la méthode de mise à jour avec les informations ci-dessus, sauf si je l'ai fait une fois. Tant que vous comprenez ce point, le reste n'est pas très différent de la forme de base de `` BFS.
027. JOI 2009 Qualifying 4-Thin Ice Crossing
Répondre
import sys
sys.setrecursionlimit(10**9)
# -------------- [valeur initiale] --------------
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)) #Obtenez la valeur maximale pouvant être atteinte à partir du point de départ
visited[start_y][start_x] = -1
return ans
if __name__ == "__main__":
# -------------- [contribution] --------------
m = int(input()) #côté
n = int(input()) #Verticale
grid = [list(map(int, input().split())) for _ in range(n)] # 1:Glace, 0:Pas de glace
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Haut, bas, gauche et droite uniquement
visited = [[-1] * m for _ in range(n)]
# -------------- [Essayez tous les points comme point de départ] --------------
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)Vous pouvez passer sans lui, mais je le laisserai pour rappel.
C'est presque le même que le formulaire de base, mais la différence est
```python
ans = max(ans, dfs(count+1, moved_y, moved_x, visited)) #Obtenez la valeur maximale pouvant être atteinte à partir du point de départ
visited[start_y][start_x] = -1
Ici seulement. Cela renverra la distance la plus longue de chaque point de départ.
Recommended Posts