建站系统排行榜,用ps软件做ppt模板下载网站有哪些,免费注册网站域名,网站公司 北京文章目录 迷宫问题 迷宫问题
定义一个二维数组 m行 * n列 #xff0c;如 4 5 数组下所示#xff1a;
int arr[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, };
它表示一个迷宫#xff0c;1表示墙壁#xff0c;0表示可以走的路#xff0c;只… 文章目录 迷宫问题 迷宫问题
定义一个二维数组 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][j1] 0:# 可以向右if (i, j1) not in pos:start_to_walk(i, j1, pos[(i,j1)])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[i1][j] 0:if (i1, j) not in pos:start_to_walk(i1, j, pos[(i1, 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
