TIL)3055脱出

この文章は、
1.未来の私がこの问题を解决したい时、过去の私はどのように问题を解决したかをあなたに教えるためです.
2.同じ問題を解決する人にアイデアを提供するため
作成されました.

🐠 ハリネズミと水を同時に探る

白駿3055脱出:https://www.acmicpc.net/problem/3055
💡 アイデア

地図のグラフ

を保存する必要があります

水の移動を格納するためにキューが必要です.
ハリネズミの移動を貯蔵する列が必要です.
合計2つのキューでブラウズします.

日増加するごとに、水とハリネズミ(水->ハリネズミ)を同時に移動します.

トマトを開くときも、ここではwhileがドア内でdayを計算し、現在のキューの長さでドアを回転させる方法を使用します.

1日が過ぎた頃は、水も動いてハリネズミも動いていたので、中を移動して水のforゲートと移動ハリネズミのforゲートが入ります.

水がこれ以上動かなくてもハリネズミを移動してDに到達するしかないので、while文の終了条件はdochiキューが空の場合です.

👀 私の答え

from collections import deque

R, C = map(int, input().split())
graph = []

for _ in range(R):
    graph.append(list(input()))

dochi = deque()
water = deque()

for i in range(R):
    for j in range(C):
        if graph[i][j] == '*':
            water.append((i, j))
        elif graph[i][j] == 'S':
            dochi.append((i, j))

day = 0
def bfs():
    global day
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while dochi:
        day += 1
        for _ in range(len(water)):
            y, x = water.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= C or ny >= R:
                    continue
                if graph[ny][nx] == '.':
                    graph[ny][nx] = day
                    water.append((ny, nx))

        for _ in range(len(dochi)):
            y, x = dochi.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= C or ny >= R:
                    continue
                if graph[ny][nx] == '.':
                    graph[ny][nx] = day
                    dochi.append((ny, nx))
                if graph[ny][nx] == 'D':
                    return day


answer = bfs()

if answer is None:
    print('KAKTUS')
else:
    print(answer)

Dに達しずwhile文が終了した場合、dfs()関数はNoneを返します.

if answer is None:
    print('KAKTUS')
else:
    print(answer)

これでプリントアウトしました.