Daily AtCoder # 31 in Python

Introduction

Last time It is a continuation of \ # 24. Today I will solve 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')

Summary

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.