Daily AtCoder # 31 in Python

Introduction

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')

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.

Recommended Posts

Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 18 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 24 in Python
Daily AtCoder # 8 in Python
Daily AtCoder # 42 in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 17 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 54 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 40 in Python
Daily AtCoder # 10 in Python
Daily AtCoder # 5 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 39 in Python
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python
Daily AtCoder # 14 in Python
Daily AtCoder # 50 in Python
Daily AtCoder # 26 in Python
Daily AtCoder # 4 in Python
Daily AtCoder # 43 in Python
Daily AtCoder # 29 in Python
Daily AtCoder # 49 in Python
Daily AtCoder # 27 in Python
Daily AtCoder # 1 in Python
Daily AtCoder # 25 in Python
Daily AtCoder # 16 in Python
Daily AtCoder # 12 in Python
Daily AtCoder # 23 in Python
Daily AtCoder # 34 in Python
Daily AtCoder # 51 in Python
Daily AtCoder # 31 in Python
Daily AtCoder # 46 in Python
Daily AtCoder # 35 in Python
Daily AtCoder # 9 in Python
Daily AtCoder # 44 in Python
Daily AtCoder # 41 in Python
Atcoder ABC164 A-C in Python
atCoder 173 Python
Python Input Note in AtCoder
Atcoder ABC167 A-D in Python
Atcoder ABC166 A-E in Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
Solve Atcoder ABC169 A-D in Python
[Python] Basic knowledge used in AtCoder
Quadtree in Python --2
Python in optimization
Metaprogramming in Python