9328キー

19145 ワード
テキストリンク

🏅 9328キー


質問する


尚根は1階に侵入し、重要な書類を盗もうとした.前のルートにある平面図には、ドキュメントのすべての場所が表示されます.ビルのドアは鍵がかかっているので、ドアを開けるには鍵が必要です.尚勤はすでに鍵の一部を持っていて、鍵の一部はビルの床に置いてあります.上根は上下左右にしか移動できません.
前のルートで盗むことができるドキュメントの最大数を求めるプログラムを作成してください.

入力

  • .:空白
  • *:壁
  • $:盗み取る書類
  • 大文字と小文字:小文字は大文字(ドア)を開ける鍵

    • ぶんせき



    問題では、尚勤は最初にビルの外にいて、ビルの縁の壁を通ってビルの内外に出入りすることができます.そのため、上下左右に1つずつ与えられた平面図を追加しなければならない.
    まず尚根が持っている鍵で平面図のドアを全部開けます.
    bfsでナビゲートすると、キーを見つけるパスとドアを開けるパスが重なる可能性があるため、キーを見つけるたびにアクセスのスキーマとキューが初期化されます.
    鍵や書類が見つかったら空きスペースに変え(.)、開門時も空きスペースに変えます.
    $があるセルに着いたら、cnt値を増やせばいいです.

    ソースコード

    import sys
import string
from collections import deque, defaultdict
input = sys.stdin.readline

def bfs(x = 0, y = 0):
    q = deque()
    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
    visited[x][y] = True
    q.append((x, y))

    res = 0
    while q:
        x, y = q.popleft()

        for nx, ny in (x-1, y), (x+1, y), (x, y+1), (x, y-1):
            if nx < 0 or ny < 0 or nx >= h + 2 or ny >= w + 2:
                continue

            if not visited[nx][ny]:
                if board[nx][ny] == '.':
                    q.append((nx, ny))

                elif board[nx][ny] == '$': # 훔칠 물건
                    res += 1
                    board[nx][ny] = '.' # 물건을 훔쳐서 빈 공간이 됨
                    q.append((nx, ny))

                elif board[nx][ny].islower(): # key
                    door[board[nx][ny].lower()] = True # 열쇠를 얻음
                    q.clear()
                    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
                    q.append((nx, ny))
                    board[nx][ny] = '.' # 열쇠를 얻었으므로 빈 공간

                elif board[nx][ny].isupper(): # door
                    if door[board[nx][ny].lower()]: # 키를 갖고 있을 경우
                        visited[nx][ny] = True
                        q.append((nx, ny))
                        board[nx][ny] = '.' # 문을 열음
                visited[nx][ny] = True

    print(res)

for _ in range(int(input())):
    h, w = map(int, input().split())

    # 빌딩 밖에서 접근이 가능하므로 한칸씩 상하좌우 확장
    board = [['.' for _ in range(w+2)]]
    for _ in range(h):
        tmp = ['.']
        tmp.extend(list(input().strip()))
        tmp.extend('.')
        board.append(tmp)
    board.append(['.' for _ in range(w+2)])

    my_keys = list(input().strip())
    door = defaultdict(bool)
    for alphabet in list(string.ascii_lowercase):
        door[alphabet] = False

    if my_keys[0] != '0':
        for key in my_keys:
            door[key] = True

    # 먼저 가진 키로 문을 다 열어 놓는다.
    for i in range(h):
        for j in range(w):
            if board[i][j].isalpha() and board[i][j].isupper():
                if door[board[i][j].lower()]:
                    board[i][j] = '.'

    bfs()
    Deep Dive 06章データ型
    メインフレームをDockerで動かす