SRM509 div.2 1000 NumberLabyrinthDiv2

NumberLabyrinthDiv2.py

class NumberLabyrinthDiv2:
    def getMinimumNumberOfMoves(self, board, r1, c1, r2, c2, K):
        R, C = len(board), len(board[0])
        INF = 10**4
        dist = [[[INF for _ in range(K+1)] for _ in range(C)] for _ in range(R)]
        dist[r1][c1][0] = 0
        que = Queue.Queue()
        que.put((r1, c1, 0))
        drc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        while que.qsize() > 0:
            r, c, k = que.get()
            if r == r2 and c == c2: return dist[r2][c2][k]
            jump = board[r][c]
            if jump == '.':
                for i in range(1, 10):
                    for dr, dc in drc:
                        nr, nc = r + dr * i, c + dc * i
                        if 0 <= nr < R and 0 <= nc < C and k < K and dist[nr][nc][k+1] > dist[r][c][k] + 1:
                            dist[nr][nc][k+1] = dist[r][c][k] + 1
                            que.put((nr, nc, k+1))
            else:
                jump = int(jump)
                if jump == 0: continue
                for dr, dc in drc:
                    nr, nc = r + dr * jump, c + dc * jump
                    if 0 <= nr < R and 0 <= nc < C and dist[nr][nc][k] > dist[r][c][k] + 1:
                        dist[nr][nc][k] = dist[r][c][k] + 1
                        que.put((nr, nc, k))
        return -1