定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[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,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围： ， 输入的内容只包含
[编程题]迷宫问题
- 热度指数：196706 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的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)
说明
注意：不能斜着走！！
# 尝试使用了BFS广度优先的思想
# 1. 每个节点考虑上下左右四个朝向，但是要注意不要和倒数第二个节点的方向相同
# 2. 如果有一条路径被率先搜索到，那他一定是最短的。因为广度优先，其余还没找到终点的路径最多只可能和你当前路径等长
import sys
import copy as cp
def solutation(maze_, n, m):
routes = [
[(0, 0)]
]
res = None
while len(routes) > 0:
new_routes = []
for route in routes:
route:list
prev_i, prev_j = -1, -1
i, j = route[-1]
if len(route) > 1:
prev_i, prev_j = route[-2]
if i == n-1 and j == m-1:
res = route
break
# 遭遇墙壁, 剪去该分支
if maze_[i][j] == 1:
continue
# 朝上进行探索
if i - 1 >= 0 and i - 1 != prev_i:
route_cp = cp.deepcopy(route)
route_cp.append((i-1, j))
new_routes.append(route_cp)
# 朝下进行探索
if i + 1 < n and i + 1 != prev_i:
route_cp = cp.deepcopy(route)
route_cp.append((i+1, j))
new_routes.append(route_cp)
# 朝左探索
if j -1 >= 0 and j -1 != prev_j:
route_cp = cp.deepcopy(route)
route_cp.append((i, j-1))
new_routes.append(route_cp)
# 朝右探索
if j +1 < m and j +1 != prev_j:
route_cp = cp.deepcopy(route)
route_cp.append((i, j+1))
new_routes.append(route_cp)
if res is not None:
break
routes = new_routes
return res
n, m = input().split()
n, m = int(n), int(m)
maze = []
for i in range(0, n):
maze.append(
[int(i) for i in sys.stdin.readline().split()]
)
route = solutation(maze, n, m)
for node in route:
x, y = node
print(f"({x},{y})")
发表于 2024-01-05 17:27:09
回复(0)
h, w = list(map(int, input().strip().split(" ")))
map_num = []
for i in range(h):
map_num.append(list(map(int, input().strip().split(" "))))
route = []
def find_route(coordi_pair, up=0, down=0, left=0, right=0):
if coordi_pair == [h - 1, w - 1]:
return 1
if up == 0 and down == 0 and left == 0 and right == 0:
down_num = (
map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
)
right_num = (
map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
)
if down_num == 0:
if (
find_route(
[coordi_pair[0] + 1, coordi_pair[1]], up=1
)
== 1
):
route.append((coordi_pair[0] + 1, coordi_pair[1]))
return 1
if right_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] + 1))
return 1
return -1
if up == 1:
down_num = (
map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
)
right_num = (
map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
)
left_num = (
map_num[coordi_pair[0]][coordi_pair[1] - 1]
if coordi_pair[1] - 1 >= 0
else 1
)
if down_num and right_num and left_num:
return -1
if down_num == 0:
if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
route.append((coordi_pair[0] + 1, coordi_pair[1]))
return 1
if right_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] + 1))
return 1
if left_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] - 1))
return 1
if down == 1:
up_num = (
map_num[coordi_pair[0] - 1][coordi_pair[1]]
if coordi_pair[0] - 1 >= 0
else 1
)
right_num = (
map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
)
left_num = (
map_num[coordi_pair[0]][coordi_pair[1] - 1]
if coordi_pair[1] - 1 >= 0
else 1
)
if up_num and right_num and left_num:
return -1
if up_num == 0:
if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
route.append((coordi_pair[0] - 1, coordi_pair[1]))
return 1
if right_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] + 1))
return 1
if left_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] - 1))
return 1
if left == 1:
up_num = (
map_num[coordi_pair[0] - 1][coordi_pair[1]]
if coordi_pair[0] - 1 >= 0
else 1
)
down_num = (
map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
)
right_num = (
map_num[coordi_pair[0]][coordi_pair[1] + 1] if coordi_pair[1] + 1 < w else 1
)
if down_num and right_num and up_num:
return -1
if down_num == 0:
if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
route.append((coordi_pair[0] + 1, coordi_pair[1]))
return 1
if right_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] + 1], left=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] + 1))
return 1
if up_num == 0:
if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
route.append((coordi_pair[0] - 1, coordi_pair[1]))
return 1
if right == 1:
up_num = (
map_num[coordi_pair[0] - 1][coordi_pair[1]]
if coordi_pair[0] - 1 >= 0
else 1
)
down_num = (
map_num[coordi_pair[0] + 1][coordi_pair[1]] if coordi_pair[0] + 1 < h else 1
)
left_num = (
map_num[coordi_pair[0]][coordi_pair[1] - 1]
if coordi_pair[1] - 1 >= 0
else 1
)
if down_num and up_num and left_num:
return -1
if down_num == 0:
if find_route([coordi_pair[0] + 1, coordi_pair[1]], up=1) == 1:
route.append((coordi_pair[0] + 1, coordi_pair[1]))
return 1
if up_num == 0:
if find_route([coordi_pair[0] - 1, coordi_pair[1]], down=1) == 1:
route.append((coordi_pair[0] - 1, coordi_pair[1]))
return 1
if left_num == 0:
if find_route([coordi_pair[0], coordi_pair[1] - 1], right=1) == 1:
route.append((coordi_pair[0], coordi_pair[1] - 1))
return 1
find_route((0, 0))
route.append((0, 0))
route.reverse()
for item in route:
print(f'({item[0]},{item[1]})')
发表于 2023-09-25 19:47:17
回复(2)
广度优先搜索（bfs), 主要还可以用来寻找最短路径，不过本题也只有一条路径
from collections import deque
maze = []
m,n = map(int,input().split())
for i in range(m):
maze.append(list(map(int,input().split())))
q = deque([[(0,0)]])
visited = [(0,0)] # 记录遍历过的点
while q:
x = q.popleft()
# 如果到达终点(m-1,n-1),输出路径
if x[-1] == (m-1,n-1):
for i in x:
print(f"({i[0]},{i[1]})")
break
# (r,c)
# 向上
if 0<= x[-1][0]-1 and maze[x[-1][0]-1][x[-1][1]] == 0:
if (x[-1][0]-1,x[-1][1]) not in visited:
q.append(x+[(x[-1][0]-1,x[-1][1])])
visited.append((x[-1][0]-1,x[-1][1]))
# 向下
if x[-1][0]+1 < m and maze[x[-1][0]+1][x[-1][1]] == 0:
if (x[-1][0]+1,x[-1][1]) not in visited:
q.append(x+[(x[-1][0]+1,x[-1][1])])
visited.append((x[-1][0]+1,x[-1][1]))
# 向左
if 0 <= x[-1][1]-1 and maze[x[-1][0]][x[-1][1]-1] == 0:
if (x[-1][0],x[-1][1]-1) not in visited:
q.append(x+[(x[-1][0],x[-1][1]-1)])
visited.append((x[-1][0],x[-1][1]-1))
# 向右
if x[-1][1]+1 < n and maze[x[-1][0]][x[-1][1]+1] == 0:
if (x[-1][0],x[-1][1]+1) not in visited:
q.append(x+[(x[-1][0],x[-1][1]+1)])
visited.append((x[-1][0],x[-1][1]+1)) 深度优先搜索（dfs），主要用来遍历所有路径 # 深度优先搜索
def fn(r,c,l=[(0,0)]):
if 0 <= c-1 and maze[r][c-1] == 0:
if (r,c-1) not in l:
fn(r,c-1,l+[(r,c-1)])
if 0 <= r-1 and maze[r-1][c] == 0:
if (r-1,c) not in l:
fn(r-1,c,l+[(r-1,c)])
if c+1 < len(maze[0]) and maze[r][c+1] == 0:
if (r,c+1) not in l:
fn(r,c+1,l+[(r,c+1)])
if r+1 < len(maze) and maze[r+1][c] == 0:
if (r+1,c) not in l:
fn(r+1,c,l+[(r+1,c)])
if r==m-1 and c==n-1:
for i in l:
print(f"({i[0]},{i[1]})")
m,n = map(int,input().split())
maze = []
for i in range(m):
maze.append(list(map(int,input().split())))
fn(0,0)
发表于 2023-07-26 14:37:24
回复(0)
bfs
def fn(lq,maze,vis):
if len(lq) > 0:
i,j = lq[0]
vis = maze[i][j]+1
if i < n-1&nbs***bsp;j < m-1:
if i+1 < n:
if maze[i+1][j] == 0:
lq.append([i+1,j])
maze[i+1][j] = vis
if j+1 < m:
if maze[i][j+1] == 0:
lq.append([i,j+1])
maze[i][j+1] = vis
if i-1 >= 0:
if maze[i-1][j] == 0:
lq.append([i-1,j])
maze[i-1][j] = vis
if j-1 >= 0:
if maze[i][j-1] == 0:
lq.append([i,j-1])
maze[i][j-1] = vis
lq.pop(0)
fn(lq,maze,vis)
n,m = list(map(int,input().split()))
maze = []
for i in range(n):
maze.append(list(map(int,input().split())))
lqueue = [[0,0]]
maze[0][0] = 2
# 标记路线 每次+1 及路线上的值为[2,3,4,5,6,7,..,n+m]
fn(lqueue,maze,maze[0][0]+1)
ans = [[n-1,m-1]]
# 从右下角遍历回左上角
while ans[-1][0] > 0&nbs***bsp;ans[-1][1] > 0:
i,j = ans[-1]
vis = maze[i][j]
if i-1 >= 0:
if maze[i-1][j] == vis-1:
ans.append([i-1,j])
continue
if j-1 >=0:
if maze[i][j-1] == vis-1:
ans.append([i,j-1])
continue
if i+1 < n:
if maze[i+1][j] == vis-1:
ans.append([i+1,j])
continue
if j+1 < m:
if maze[i][j+1] == vis-1:
ans.append([i,j+1])
continue
ans.reverse()
for item in ans:
print(f'({item[0]},{item[1]})')
发表于 2023-07-21 21:35:09
回复(0)
dfs
def dfs(maze_mat,routes,p = (0,0)):
routes.append(p)
if((p[0] == len(maze_mat)-1)and(p[1]==len(maze_mat[0])-1)): return True
if((p[0] < 0) or (p[1] < 0) or (p[0] >= len(maze_mat)) or (p[1]>=len(maze_mat[0])) or (maze_mat[p[0]][p[1]]==1)):
routes.pop()
return False
for dir_vec in ((1,0),(-1,0),(0,1),(0,-1)):
next_p = (p[0]+dir_vec[0],p[1]+dir_vec[1])
if(next_p in routes): continue # 防成环
if(dfs(maze_mat,routes,next_p) == True): return True
routes.pop()
return False
maze_height = int(input().split()[0])
maze_mat = []
for i in range(maze_height):
maze_mat.append(list(map(int,input().split())))
routes = []
dfs(maze_mat,routes)
for p in routes: print(str(p).replace(" ",""))
发表于 2023-07-21 17:18:22
回复(0)
#小分享一波思路
# 接收行列参数
a, b = map(int, input().split())
route_list = []
for i in range(a):
route_list.append(list(map(int, input().split())))
lis = []
lis.append((0,0))
def check_loc(x,y):
# 防止移动越界
global a
global b
if x < 0:
x = 0
elif x >= a-1:
x = a-1
if y < 0:
y = 0
elif y >= b-1:
y = b-1
return x,y
while True:
x, y = lis[-1]
if x == a - 1 and y == b -1:
for i in lis:
print(f"({i[0]},{i[1]})")
break
# 向右移动
x1,y1 = check_loc(x,y+1)
if route_list[x1][y1] == 0:
lis.append((x1,y1))
route_list[x1][y1] = 2
continue
# 向下移动
x1,y1 = check_loc(x+1,y)
if route_list[x1][y1] == 0:
lis.append((x1,y1))
route_list[x1][y1] = 2
continue
# 向上移动
x1,y1 = check_loc(x-1,y)
if route_list[x1][y1] == 0:
lis.append((x1,y1))
route_list[x1][y1] = 2
continue
# 向左移动
x1,y1 = check_loc(x,y-1)
if route_list[x1][y1] == 0:
lis.append((x1,y1))
route_list[x1][y1] = 2
continue
lis.pop()
发表于 2023-07-09 12:42:53
回复(1)
n, m = map(int, input().split())
nums = []
for i in range(n):
nums.append([int(i) for i in input().split()])
route = []
def dfs(i, j):
if nums[i][j] == 1:
return False
if i == n - 1 and j == m - 1:
return True
nums[i][j] = 1
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if -1 < x < n and -1 < y < m and dfs(x, y):
route.append((x, y))
return True
dfs(0, 0)
for i in [(0, 0)] + route[::-1]:
print(f"({i[0]},{i[1]})")
发表于 2023-06-06 17:42:16
回复(1)
# 采用动态规划的方法
import sys
'''
1. dp[i][j]表示走到 [i,j]这个位置需要的最小步数,初始赋值一个达不到的最大值，此处采用 m*n+1, dp[0][0]=1
2. 递推关系 dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i+1][j]+1, dp[i][j+1]+1)，即判断[i,j]上下左右四个方向
的最小值中一步再加一步
3. 更新dp[i][j],有些值可能第一次循环没有更新到，所以需要多次循环，直到dp[i][j]没有变化。此处采用hash存储可能更加节省计算量
'''
# 读取数据，并给动态规划赋值
m, n = map(int, input().split())
path = []
maze = []
dp = []
max_val = m * n + 1
for i in range(m):
maze.append(list(map(int, input().split())))
dp.append([max_val] * n)
# 更新dp[i][j]
has_updated = True
dp[0][0] = 1
while has_updated:
has_updated = False
for i in range(m):
for j in range(n):
if maze[i][j] == 1: # 障碍物，用最大值代替
dp[i][j] = max_val
continue
elif dp[i][j] < max_val: # 已经更新过的路径不再更新，如果要求最小路径，可能需要调整。
continue
else:
prev = dp[i][j]
# 四个方向上的值，抵达不了的用最大值代替
a = max_val if j == 0 else dp[i][j - 1] + 1
b = max_val if i == 0 else dp[i - 1][j] + 1
c = max_val if i == m - 1 else dp[i + 1][j] + 1
d = max_val if j == n - 1 else dp[i][j + 1] + 1
dp[i][j] = min(a, b, c, d)
if prev != dp[i][j]: # 判断是否存在元素更新
has_updated = True
# 基于dp[i][j]反向计算来时候的路径，存储到path中
i = m - 1
j = n - 1
path.append([i, j])
while i+j>0:
if i > 0 and dp[i - 1][j] == dp[i][j] - 1:
path.append([i - 1, j])
i -= 1
elif j > 0 and dp[i][j - 1] == dp[i][j] - 1:
path.append([i, j - 1])
j -= 1
elif i < m - 1 and dp[i + 1][j] == dp[i][j] - 1:
path.append([i + 1, j])
i += 1
elif j < n - 1 and dp[i][j + 1] == dp[i][j] - 1:
path.append([i, j + 1])
j += 1
#逆向打印path
for i, j in path[::-1]:
print("({},{})".format(i, j))
发表于 2023-05-24 20:44:49
回复(0)
def main(): N, M = map(int, input().split()) maze = [list(map(int, input().split())) for i in range(int(N))] start = (0,0) path = [] def dfs(maze, start, visit): if start[0] < 0 or start[0] >= N or start[1] < 0 or start[1] >= M or maze[start[0]][ start[1]] == 1 or start in visit: return False visit.append(start) if start[0] == N - 1 and start[1] == M - 1: return True if dfs(maze, (start[0], start[1] + 1), visit) or dfs(maze, (start[0], start[1] - 1), visit) or dfs(maze, ( start[0] + 1, start[1]), visit) or dfs(maze, (start[0] - 1, start[1]), visit): return True visit.pop() return False if dfs(maze, start, path): [print(f"({path[i][0]},{path[i][1]})") for i in range(0,len(path))] if __name__=="__main__": main()
发表于 2023-05-12 18:24:23
回复(0)
递归法 思想很简单 对一个点的上下左右去遍历 把走过的点标记为1 无法前进就退回到可变向的位置
n1, n2 = map(int, input().strip().split(" "))
result_list = []
map_0 = [[0 for _ in range(n2)] for _ in range(n1)]
for i in range(n1):
map_0[i] = list(map(int, input().strip().split(" ")))
def is_valid_one_row(i):
if i in [j for j in range(n1)]:
return True
else:
return False
def is_valid_one_col(i):
if i in [j for j in range(n2)]:
return True
else:
return False
def is_valid_two(i, j):
if is_valid_one_row(i) and is_valid_one_col(j):
if map_0[i][j] == 0:
result_list.append("(" + str(i) + "," + str(j) + ")")
return True
else:
return False
return False
def move_four_direct(i, j):
map_0[i][j] = 1
if is_valid_two(i - 1, j):
if (i - 1, j) == (n1 - 1, n2 - 1):
return True
else:
if move_four_direct(i - 1, j):
return True
else:
result_list.append("(" + str(i - 1) + "," + str(j) + "")
map_0[i - 1][j] = 0
if is_valid_two(i + 1, j):
if (i + 1, j) == (n1 - 1, n2 - 1):
return True
else:
if move_four_direct(i + 1, j):
return True
else:
result_list.append("(" + str(i + 1) + "," + str(j) + "")
map_0[i + 1][j] = 0
if is_valid_two(i, j - 1):
if (i, j - 1) == (n1 - 1, n2 - 1):
return True
else:
if move_four_direct(i, j - 1):
return True
else:
result_list.append("(" + str(i) + "," + str(j - 1) + "")
map_0[i][j - 1] = 0
if is_valid_two(i, j + 1):
if (i, j + 1) == (n1 - 1, n2 - 1):
return True
else:
if move_four_direct(i, j + 1):
return True
else:
result_list.append("(" + str(i) + "," + str(j + 1) + "")
map_0[i][j + 1] = 0
return False
result_list.append("(0,0)")
move_four_direct(0, 0)
count_each = {1: [], 2: []}
for each in result_list:
count_each[result_list.count(each)].append(each)
for each in count_each[1]:
print(each)
发表于 2023-04-30 10:08:26
回复(0)
m, n = list(map(int, input().split()))
array = []
for _ in range(m):
array.append(list(map(int, input().split())))
used = [[0]*n for _ in range(m)] # 标记坐标是否被使用，0代表未使用，1代表使用
used[0][0] = 1 # 初始从（0，0）开始，标记为1
res = []
def dfs(x,y,path):
if x == m - 1 and y == n - 1: # 到达右下角时获取路径
res.append(path)
return
for a,b in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]: # 向四个方向试探
if 0 <= a < m and 0 <= b < n and array[a][b] == 0 and used[a][b] == 0:
used[a][b] = 1
dfs(a,b,path+[(a,b)])
used[a][b] = 0
dfs(0,0,[(0,0)])
for i in res[0]:
print('(' + str(i[0]) + ',' + str(i[1]) + ')')
发表于 2023-04-23 23:33:50
回复(0)
这里给出一个不同于递归的解法：利用解的存在性和唯一性。
定理一：如果迷宫有解，则不断贴着右边的墙走，一定能走到出口。则每一步选择的优先级就是（右-前-左-后）。由于对称性，（左-前-右-后）也是可以的，这里选前者。
定理二：由于最短路径存在且唯一，由定理一得到的路径，去掉重复（走进死胡同又走出来），即得到最短路径。
代码如下：
import sys
n,m = list(map(int, input().split()))
maze = [0 for j in range(n)]
for i in range(n):
row = list(map(int, input().split()))
maze[i] = row
# initial steps
pre = [0,0]
if maze[1][0] == 0:
cur = [1,0]
else:
cur = [0,1]
# record path
history = []
history.append(pre)
history.append(cur)
# to see if the next step is inside the maze
def isin(coord,dim):
x,y = coord[0],coord[1]
n,m = dim[0],dim[1]
if x < 0&nbs***bsp;x > n-1&nbs***bsp;y < 0&nbs***bsp;y > m-1:
return False
else:
return True
# add coordinate
def addCoord(t1,t2):
t = list(t1[i]+t2[i] for i in range(len(t1)))
return t
# deduct coordinate
def minusCoord(t1,t2):
t = list(t1[i]-t2[i] for i in range(len(t1)))
return t
# given moving direction, determine left and right
def right_or_left(front): # notice here i,j mean row,column, not x.y!
if front == [1,0]:
return [0,-1],[0,1]
elif front == [-1,0]:
return [0,1],[0,-1]
elif front == [0,1]:
return [1,0],[-1,0]
elif front == [0,-1]:
return [-1,0],[1,0]
# main loop
while cur != [n-1,m-1]:
# find the moving direction
front = minusCoord(cur,pre) # move front
back = minusCoord(pre,cur)
right,left = right_or_left(front)
# move priority, right - front - left - back: keep moving rightwards whenever possible
for i in [right,front,left,back]:
next = addCoord(cur,i)
if isin(next, [n,m]) and maze[next[0]][next[1]] == 0: # if moveable,
pre = cur
cur = next
history.append(cur)
break
# there might be duplicates due to deadends, remove
history_no_rep = []
i = 0
while i < len(history):
history_no_rep.append(history[i])
i += 1
for j in range(i,len(history)):
if history[i-1] == history[j]:
i = j + 1
# output
for i in history_no_rep:
x = str(i[0])
y = str(i[1])
print('(' + x + ',' + y + ')')
发表于 2023-04-23 10:16:51
回复(0)
rc=input().strip().split(' ')
row,col=int(rc[0]),int(rc[1])
maze=[]
for i in range(row):
maze.append(input().strip().split(' '))
res=[]
walked_path=[]
def testify(i,j):
if 0<=i<row and 0<=j<col and [i,j] not in walked_path and maze[i][j]=='0':
walked_path.append([i,j])
if walk(i,j):
res.append([i,j])
return True
def walk(i,j):
if i==row-1 and j==col-1:
return True
if testify(i+1,j):
return True
if testify(i-1,j):
return True
if testify(i,j+1):
return True
if testify(i,j-1):
return True
return False
walk(0,0)
print('(0,0)')
for i in res[::-1]:
print('('+str(i[0])+','+str(i[1])+')')
发表于 2023-04-21 15:37:35
回复(0)
问题信息
难度：
41条回答
4063收藏
100341浏览
通过挑战的用户
查看代码-
2023-03-11 16:31:38
-
2023-03-09 00:06:20
-
2023-03-05 12:23:54
-
2023-03-04 20:36:49 -
2023-03-04 13:41:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
