题解 | #地下迷宫#

import sys

inputs = []
for line in sys.stdin:
    inputs.extend(list(map(int, line.split())))

def escape_matrix(nums):
    n, m, p = nums[0], nums[1], nums[2]
    new_nums = nums[3:]
    matrix = [new_nums[i*m:(i+1)*m] for i in range(n)]
    transfer_matrix = [[None for _ in range(m)] for _ in range(n)]

    start, end = (0, 0), (0, m-1)
    u, v, d = 3, 1, 0
    move = [(1, 0, u), (-1, 0, d), (0, 1, v), (0, -1, v)]

    path = [(0, 0, p)]
    flag = True

    transfer_matrix[0][0] = (0, 0, p)

    while path and flag:
        cur = path.pop(0)

        for k in range(4):
            next_i = cur[0] + move[k][0]
            next_j = cur[1] + move[k][1]
            next_p = cur[2] - move[k][2]

            if not (0 <= next_i < n and 0 <= next_j < m):
                continue
            if matrix[next_i][next_j] != 1 or next_p < 0:
                continue
            if transfer_matrix[next_i][next_j] is not None and transfer_matrix[next_i][next_j][2] >= next_p:
                continue

            path.append((next_i, next_j, next_p))
            transfer_matrix[next_i][next_j] = (cur[0], cur[1], cur[2])

        if transfer_matrix[end[0]][end[1]] is not None:
            flag = False

    if transfer_matrix[end[0]][end[1]] is not None:
        res = []
        x, y = end
        while (x, y) != start:
            res.append(f'[{x},{y}]')
            x, y = transfer_matrix[x][y][0:2]
        res.append(f'[{start[0]},{start[1]}]')
        return ','.join(reversed(res))
    else:
        return "Can not escape!"

print(escape_matrix(inputs))