迷宮問題

定義一個二維數組 m行 * n列 ，如 4 × 5 數組下所示：

int arr[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
};

它表示一個迷宮，1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，找出從左上角到右下角的路線。入口點為[0,0]，既該點是可以走的路。

輸入描述：
輸入兩個整數，分別表示二維數組的行數，列數。再輸入相應的數組，其中的1表示墻壁，0表示可以走的路。數據保證有唯一解,不考慮有多解的情況，即迷宮只有一條通道。

輸出描述：
左上角到右下角的最短路徑，格式如樣例所示。

示例1
輸入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
輸出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
?
示例2
輸入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
輸出：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

python，廣度優先

• 每個點在條件允許的情況下搜索左右上下四個方向；
• 走到一個點后，遞歸搜索剩下的路；
• 最后輸出字符串；

def start_to_walk(i, j, pos=[(0,0)]):if j + 1 < n and arr[i][j+1] == 0:# 可以向右if (i, j+1) not in pos:start_to_walk(i, j+1, pos+[(i,j+1)])if j >= 1 and arr[i][j-1] == 0:if (i, j-1) not in pos:start_to_walk(i, j-1, pos+[(i, j-1)])if i + 1 < m and arr[i+1][j] == 0:if (i+1, j) not in pos:start_to_walk(i+1, j, pos+[(i+1, j)])if i >= 1 and arr[i-1][j] == 0:if (i-1, j) not in pos:start_to_walk(i-1, j, pos+[(i-1, j)])if (i,j) == (m-1, n-1):for p in pos:print("("+str(p[0])+","+str(p[1])+")")while True:try:m, n = input().strip().split()m = int(m)n = int(n)arr = []for m_ in range(m):temp = input().strip().split()temp = list(map(int, temp))arr.append(temp)start_to_walk(0,0)except:break