Last time It is a continuation of \ # 24. Today I will solve ARC031-B.
#31 ARC031-B
** Thoughts ** At first I didn't know how to write DFS, so I read article. However, when I searched, only the one using the recursive function came out, so this time I will solve it using stack (I only know that). The difference from the previous problem of this problem is that no goal is set. At first I stumbled on this. Because there is no goal, the end condition of the search could not be set well. So think about your goals. This problem is asking if all **'o's are connected **, so the goal is that the number of'o's searched is the sum of the input'o's. In addition, landfill is calculated with double for. ** Please forgive that the variable name is not dirty. ** **
from collections import deque
field = [list(input()) for _ in range(10)] #If you receive it with str, an error will be thrown at the time of landfill, so make it a list
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 #Calculate steps
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 #Landfill'o'Will increase
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' #Return after landfill
ume = False
count_step -= 1
print('NO')
I want to get used to it little by little and become able to use it. If you have any interesting problems, please rip. See you again, good night.
Recommended Posts