Daily AtCoder # 31 en Python

introduction

Dernière fois C'est une continuation de \ # 24. Aujourd'hui, je vais résoudre ARC031-B.

** Pensées ** Au début, je ne savais pas comment écrire DFS, alors j'ai lu Article. Cependant, lorsque j'ai cherché, seul celui utilisant la fonction récursive est sorti, donc cette fois je vais le résoudre en utilisant stack (je le sais seulement). La différence avec le problème précédent de ce problème est qu'aucun objectif n'est fixé. Au début, je suis tombé sur cela. Comme il n'y a pas d'objectif, je n'ai pas pu définir correctement la condition de fin de la recherche. Alors pensez à vos objectifs. Ce problème demande si tous les ** 'o sont connectés **, donc le but est que le nombre de' o 'recherché soit la somme des entrées'o. De plus, la mise en décharge est calculée avec un double pour. ** Veuillez pardonner que le nom de la variable n'est pas sale. ** **

from collections import deque
field = [list(input()) for _ in range(10)] #Si vous le recevez avec str, cela générera une erreur au moment de la mise en décharge, alors faites-en une 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 #Calculer les étapes
    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 #Mis en décharge'o'Augmentera
            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' #Retour après mise en décharge
            ume = False
            count_step -= 1
print('NO')

Résumé

Je veux m'y habituer petit à petit et devenir capable de m'en servir. Si vous rencontrez des problèmes intéressants, veuillez déchirer. A bientôt, bonne nuit.