Letztes Mal Es ist eine Fortsetzung von \ # 24. Heute werde ich [ARC031-B] lösen (https://atcoder.jp/contests/arc031/tasks/arc031_2).
#31 ARC031-B
** Gedanken ** Zuerst wusste ich nicht, wie man DFS schreibt, also las ich Artikel. Als ich jedoch suchte, kam nur derjenige heraus, der die rekursive Funktion verwendete, und dieses Mal werde ich sie mit dem Stapel lösen (das weiß ich nur). Der Unterschied zu dem vorherigen Problem dieses Problems besteht darin, dass kein Ziel festgelegt wurde. Zuerst bin ich darauf gestoßen. Da es kein Ziel gibt, konnte ich die Endbedingung der Suche nicht gut festlegen. Denken Sie also über Ihre Ziele nach. Bei diesem Problem wird gefragt, ob alle ** 'o's verbunden sind **. Das Ziel ist also, dass die Anzahl der gesuchten O's die Summe der eingegebenen O's ist. Zusätzlich wird die Deponie mit double for berechnet. ** Bitte verzeihen Sie, dass der Variablenname nicht verschmutzt ist. ** **.
from collections import deque
field = [list(input()) for _ in range(10)] #Wenn Sie es mit str erhalten, wird zum Zeitpunkt der Deponierung ein Fehler ausgegeben. Machen Sie es also zu einer Liste
def dfs(field,visited_list,stack):
step = 0
while len(stack) > 0:
h, w = stack.pop()
for j, k in ([1,0],[-1,0],[0,1],[0,-1]):
new_h, new_w = h+j, w+k
if new_h < 0 or new_h >= 10 or new_w < 0 or new_w >= 10:
continue
if field[new_h][new_w] != 'x' and visited_list[new_h][new_w] == 0:
visited_list[new_h][new_w] = 1
stack.append([new_h,new_w])
step += 1 #Schritte berechnen
return step
count_step = 0
for i in range(10):
for j in range(10):
if field[i][j] == 'o':
count_step += 1
ume = 0
for i in range(10):
for j in range(10):
if field[i][j] != 'o':
field[i][j] = 'o'
count_step += 1 #Deponiert'o'Wird steigen
ume = True
visited_list = [[0]*10 for _ in range(10)]
visited_list[i][j] = 1
stack = deque([[i,j]])
step = dfs(field,visited_list,stack)
step += 1
if step == count_step:
print('YES')
quit()
if ume:
field[i][j] = 'x' #Rückkehr nach der Deponie
ume = False
count_step -= 1
print('NO')
Ich möchte mich nach und nach daran gewöhnen und es benutzen können. Wenn Sie interessante Probleme haben, rippen Sie bitte. Wir sehen uns wieder, gute Nacht.
Recommended Posts