题解 | 迷宫问题

import sys
from functools import lru_cache

def check_boundary(i, j):
    return  i < row and i >= 0 and j < col and j >= 0


def dfs(i,j):
    res = False
    visited[i][j] = 1
    if matrix[i][j] == '1':
        res = False
        return res
    if i == dest[0] and j == dest[1]:
        res = True
    for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        i2, j2 = i+dx, j+dy
        if check_boundary(i2, j2) and visited[i2][j2] == 0:
            if dfs(i2, j2):
                res = True
    if res == True:
        path.append((i,j))
    return res
   

raw_input = []
for i,line in enumerate(sys.stdin):
    raw_input.append(line.strip())

dest = [int(i) - 1 for i in raw_input[0].split(' ')]
path = []
matrix = [string.split(' ') for string in raw_input[1:]]
row, col = len(matrix), len(matrix[0])
visited = [[0]*col for _ in range(row)]
dfs(0, 0)
for p in path[::-1]:
    print(f'({p[0]},{p[1]})')