题解 | #迷宫问题#

• 广度优先搜索;
• 把访问过的位置标记为1;

def bfs(A, i, j):
    m,n = len(A), len(A[0])
    if i == m-1 and j == n-1:
        return 0, [(i,j)]
    if i < 0 or i >= m or j < 0 or j >= n or A[i][j] == '1':
        return m*n, None
    A[i][j] = '1'
    d_min = m*n
    p_min = []
    for (ai,aj) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
        d_pq, p_pq = bfs(A, ai, aj)
        if d_pq < d_min:
            d_min = d_pq
            p_min = p_pq
    return d_min + 1, [(i,j)] + p_min


def process_one_case():
	# 处理输入
    m,n = list(map(int, input().split(' ')))
    A = []
    for _ in range(m):
        A.append(input().split(' '))

	# 广度有限搜索
    d_00, p_00 = bfs(A, 0, 0)
    
    # 输出结果
    for pair in p_00:
        print("({},{})".format(pair[0],pair[1]))
    
    
while True:
    try:
        process_one_case()
    except:
        break