题解 | #迷宫问题#
迷宫问题
http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
- 广度优先搜索;
- 把访问过的位置标记为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