HJ43_迷宫问题_回溯

发布时间 2023-03-24 18:14:15作者: Aneverforget

¥问题:探索沿着0路径走出矩阵迷宫。

¥思路:

1、第一个站位点为(0,0)坐标,站在(0,0)坐标向分别向左右上下探索,如探索到1则回溯重新探索0路径。

2、比如向右走几步后,检测到了右上下都是1,此时回溯。注意在探索过程中,有可能探索重复的死胡同,所以需要用pos list记录探索过的左边,探索重新探索。

3、在探索过程中有可能迭代超出边界,因此需要对边界左边进行界定和判断。

¥几大注意点:

1、自定义函数track中,采用了5个if判断,不能错用if,elif,否则在回溯过程,跳过分支探索,无法继续探索,导致程序出错。

¥奇怪的报错:

1、在测试过程一直报下图错误,(但是很确定,两个大小对比都是int类型没有tuple类型,只能一行行地替换查找,最后发现问题所在,但依然不知道问题原因)。把原来第一个if判断放在最后一个,或者把输出的for循环改成k就不再出现类型报错。!!原因是什么?

2、tuple的创建。如,a=【(1,2),(3,4)】创建tuple列表,tuple的逗号后无空格,但是输出时,tuple的逗号后有空格。所以一字符串的方式重新整理输出格式。

 

 

 

 

 

 

 

 1 import sys
 2 m,n=list(map(int,sys.stdin.readline().strip().split()))
 3 l=[]
 4 for i in sys.stdin:
 5     l.append(list(map(int,i.strip().split())))
 6 #探索路径,往下、往右、往左、往上
 7 pos=[(0,0)]
 8 def track(i,j,pos):
 9     if i<m-1 and l[i+1][j] == 0:#向下
10         if (i+1,j) not in pos:
11             track(i+1,j,pos+[(i+1,j)])
12     if j < n-1 and l[i][j+1]==0:#向右
13         if (i,j+1) not in pos:
14             track(i,j+1,pos+[(i,j+1)])
15     if j>0 and l[i][j-1]==0:#向左
16         if (i,j-1) not in pos:
17             track(i,j-1,pos+[(i,j-1)])
18     if i>0 and l[i-1][j]==0:#向上
19         if (i-1,j) not in pos:
20             track(i-1,j,pos+[(i-1,j)])
21     if i==m-1 and j==n-1:
22         for i in pos:
23             #print(i)
24             print("("+str(i[0])+","+str(i[1])+")")
25     return
26 track(0,0,pos)