14442号-壁を破って移動2

1661 ワード
algorithm baekjoon python テキストリンク

質問:https://www.acmicpc.net/problem/14442

質問する


破壁移動1題とほぼ同じです.しかしk号まで破壊できることを考えると、前の問題とは違います.

に答える


3 Dマトリクスnxmxkを用いてdpを生成し,bfs回りにカウントした.
隣接する壁であれば、dp[idx+1][y][x]にカウンタを保存し、qにもidx+1を入れる.
そうでなければ、dp[idx][y][x]にカウントを格納し、qにもidxを入力することができる.

code

from collections import deque

n,m,k = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int,input())))


dp = [[[-1] * m for _ in range(n)] for _ in range(k+1)]

def bfs():
    q = deque()
    q.append((0,0,0,0))
    dp[0][0][0] = 0
    dy = [0,0,-1,1]
    dx = [-1,1,0,0]
    answer = 9999999
    while q:
        y,x,idx,cnt = q.popleft()
        if y==n-1 and x==m-1:
            answer = min(answer,cnt)
            continue
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if not (0<=ny<n and 0<=nx<m):
                continue
            if dp[idx][ny][nx]!=-1:
                continue
            if board[ny][nx]==0:
                dp[idx][ny][nx]=cnt+1
                q.append((ny,nx,idx,cnt+1))
            else:
                if idx<k:
                    dp[idx+1][ny][nx]=cnt+1
                    q.append((ny,nx,idx+1,cnt+1))
    if answer==9999999:
        return -1
    else:
        return answer+1
print(bfs())

result



最初の場所も時間をあげるのを忘れて、2回間違えました...
JAva基本功強固-変数
Kotlinベース#8 RecycleViewとAdapter