[已解决]Python路径问题，求解！

Bella666

[['SE', 'SW', 'NE', 'NW', 'NW', 'SE', 'NE'],
['NE', 'NE', 'NW', 'SW', 'NE', 'SE', 'SW'],
['SW', 'SE', 'NE', 'SW', 'SE', 'NE', 'SW'],
['SW', 'SE', 'SE', 'SW', 'SW', 'SW', 'NE'],
['SW', 'NW', 'SE', 'SE', 'SE', 'NW', 'SW'],
['NE', 'SW', 'NE', 'SW', 'SW', 'SE', 'NW'],
['NW', 'SW', 'NW', 'NW', 'SE', 'SE', 'SW']]
图片显示的是NE， NW， SE， SW可以走的方向，优先对角线，然后水平，然后垂直，
寻找从这个二维矩阵的中心（3，3）到四个角（0，0），（0，6），（6，0），（6，6）的最短路径，并输出最短路径，如果没有就不用写。
例如：
There is no path to (0, 0)
There is no path to (0,6)
The preferred path to (6, 6) is:
   [(3, 3), (4,3), (4, 4), (5, 5), (6, 6)]
The preferred path to (6,0) is:
   [(3, 3), (4,2), (5,3), (6,2), (5,1), (6,0)]

最佳答案

月排行榜 / 总排行榜

claws0n

2018-10-6 06:06:35

1. maze = [['SE', 'SW', 'NE', 'NW', 'NW', 'SE', 'NE'],
   
2.         ['NE', 'NE', 'NW', 'SW', 'NE', 'SE', 'SW'],
   
3.         ['SW', 'SE', 'NE', 'SW', 'SE', 'NE', 'SW'],
   
4.         ['SW', 'SE', 'SE', 'SW', 'SW', 'SW', 'NE'],
   
5.         ['SW', 'NW', 'SE', 'SE', 'SE', 'NW', 'SW'],
   
6.         ['NE', 'SW', 'NE', 'SW', 'SW', 'SE', 'NW'],
   
7.         ['NW', 'SW', 'NW', 'NW', 'SE', 'SE', 'SW']]
   
8. 
   
9. def solveMaze(start, dest):
   
10.     paths = []
    
11.     r = len(maze)
    
12.     c = len(maze[0])
    
13.     limit = (abs(start[0]-dest[0]) + abs(start[1]-dest[1]))
    
14. 
    
15.     def solvingmaze(path, dest):
    
16.         nonlocal paths, r, c, limit
    
17. 
    
18.         if path[-1] == dest:
    
19.             paths.append(path[:])
    
20.             return
    
21.                
    
22.         x = path[-1][0]
    
23.         y = path[-1][1]
    
24.         if maze[x][y] == 'NE':
    
25.             route = [[-1,1], [0,1], [-1,0]]
    
26.         elif maze[x][y] == 'NW':
    
27.             route = [[-1,-1], [0,-1], [-1,0]]
    
28.         elif maze[x][y] == 'SE':
    
29.             route = [[1,1], [0,1], [1,0]]
    
30.         elif maze[x][y] == 'SW':
    
31.             route = [[1,-1], [0,-1], [1,0]]
    
32.             
    
33.         for each in route:
    
34.             node = (path[-1][0] + each[0], path[-1][1] + each[1])
    
35.             if -1 not in node and r != node[0] and c != node[1]:
    
36.                 if len(path) > limit:
    
37.                     return
    
38.                 if node in path:
    
39.                     break
    
40.                 path.append(node)
    
41.                 solvingmaze(path,dest)
    
42.                 path.pop(-1)
    
43.    
    
44.     solvingmaze( [ (start[0], start[1]) ] , dest)
    
45.     if len(paths) > 1:
    
46.         m = r*c
    
47.         for each in paths:
    
48.             if m > len(each):
    
49.                 m = len(each)
    
50.                 i = paths.index(each)
    
51.         print('The preferred path to {} is:'.format(dest))
    
52.         print(paths[i])
    
53.     else:
    
54.         print('There is no path to {}'.format(dest))
    
55. 
    
56. # main()
    
57. solveMaze((3,3),(0,0))
    
58. solveMaze((3,3),(0,6))
    
59. solveMaze((3,3),(6,0))
    
60. solveMaze((3,3),(6,6))

复制代码

1. There is no path to (0, 0)
   
2. There is no path to (0, 6)
   
3. The preferred path to (6, 0) is:
   
4. [(3, 3), (4, 2), (5, 3), (6, 2), (5, 1), (6, 0)]
   
5. The preferred path to (6, 6) is:
   
6. [(3, 3), (4, 3), (4, 4), (5, 5), (6, 6)]

复制代码

可以知道姐姐读哪一间吗？怎么那么恐怖？

跳转到最佳答案楼层

RIXO

为什么你总能找到这种题！！！

claws0n

1. maze = [['SE', 'SW', 'NE', 'NW', 'NW', 'SE', 'NE'],
   
2.         ['NE', 'NE', 'NW', 'SW', 'NE', 'SE', 'SW'],
   
3.         ['SW', 'SE', 'NE', 'SW', 'SE', 'NE', 'SW'],
   
4.         ['SW', 'SE', 'SE', 'SW', 'SW', 'SW', 'NE'],
   
5.         ['SW', 'NW', 'SE', 'SE', 'SE', 'NW', 'SW'],
   
6.         ['NE', 'SW', 'NE', 'SW', 'SW', 'SE', 'NW'],
   
7.         ['NW', 'SW', 'NW', 'NW', 'SE', 'SE', 'SW']]
   
8. 
   
9. def solveMaze(start, dest):
   
10.     paths = []
    
11.     r = len(maze)
    
12.     c = len(maze[0])
    
13.     limit = (abs(start[0]-dest[0]) + abs(start[1]-dest[1]))
    
14. 
    
15.     def solvingmaze(path, dest):
    
16.         nonlocal paths, r, c, limit
    
17. 
    
18.         if path[-1] == dest:
    
19.             paths.append(path[:])
    
20.             return
    
21.                
    
22.         x = path[-1][0]
    
23.         y = path[-1][1]
    
24.         if maze[x][y] == 'NE':
    
25.             route = [[-1,1], [0,1], [-1,0]]
    
26.         elif maze[x][y] == 'NW':
    
27.             route = [[-1,-1], [0,-1], [-1,0]]
    
28.         elif maze[x][y] == 'SE':
    
29.             route = [[1,1], [0,1], [1,0]]
    
30.         elif maze[x][y] == 'SW':
    
31.             route = [[1,-1], [0,-1], [1,0]]
    
32.             
    
33.         for each in route:
    
34.             node = (path[-1][0] + each[0], path[-1][1] + each[1])
    
35.             if -1 not in node and r != node[0] and c != node[1]:
    
36.                 if len(path) > limit:
    
37.                     return
    
38.                 if node in path:
    
39.                     break
    
40.                 path.append(node)
    
41.                 solvingmaze(path,dest)
    
42.                 path.pop(-1)
    
43.    
    
44.     solvingmaze( [ (start[0], start[1]) ] , dest)
    
45.     if len(paths) > 1:
    
46.         m = r*c
    
47.         for each in paths:
    
48.             if m > len(each):
    
49.                 m = len(each)
    
50.                 i = paths.index(each)
    
51.         print('The preferred path to {} is:'.format(dest))
    
52.         print(paths[i])
    
53.     else:
    
54.         print('There is no path to {}'.format(dest))
    
55. 
    
56. # main()
    
57. solveMaze((3,3),(0,0))
    
58. solveMaze((3,3),(0,6))
    
59. solveMaze((3,3),(6,0))
    
60. solveMaze((3,3),(6,6))

复制代码

1. There is no path to (0, 0)
   
2. There is no path to (0, 6)
   
3. The preferred path to (6, 0) is:
   
4. [(3, 3), (4, 2), (5, 3), (6, 2), (5, 1), (6, 0)]
   
5. The preferred path to (6, 6) is:
   
6. [(3, 3), (4, 3), (4, 4), (5, 5), (6, 6)]

复制代码

可以知道姐姐读哪一间吗？怎么那么恐怖？

Bella666

claws0n 发表于 2018-10-6 06:06
可以知道姐姐读哪一间吗？怎么那么恐怖？

老师还说，so easy 呢！

claws0n

Bella666 发表于 2018-10-6 13:50
老师还说，so easy 呢！

这题有一定的难度。递归就算了，还排列组合的递归……
不告知？

Bella666

RIXO 发表于 2018-10-6 00:51
为什么你总能找到这种题！！！

老师给的啊

RIXO

Bella666 发表于 2018-10-6 14:38
老师给的啊

你不会是那种专门学算法的把

claws0n

RIXO 发表于 2018-10-6 16:35
你不会是那种专门学算法的把

不像
都是作业吧

Bella666

claws0n 发表于 2018-10-6 18:59
不像
都是作业吧

这只是Python课的作业

claws0n

Bella666 发表于 2018-10-7 21:39
这只是Python课的作业

我知道 assignment 2, due by October 28。只是想知道姐姐读哪一间，么么 ^_^

Bella666

claws0n 发表于 2018-10-7 21:45
我知道 assignment 2, due by October 28。只是想知道姐姐读哪一间，么么 ^_^

这个私聊

claws0n

Bella666 发表于 2018-10-7 23:19
这个私聊

姐姐，有问题要讲呀，其他题的

1. def solveMaze(start, dest):
   
2.     paths = []
   
3.     r = len(maze)
   
4.     c = len(maze[0])
   
5.     limit = r*c
   
6.     def solvingmaze(path, dest):
   
7.         nonlocal paths, r, c, limit
   
8.         
   
9.         if path[-1] == dest:
   
10.             paths.append(path[:])
    
11.             return
    
12.                
    
13.         x = path[-1][0]
    
14.         y = path[-1][1]
    
15.         if maze[x][y] == 'NE':
    
16.             route = [[-1,1], [0,1], [-1,0]]
    
17.         elif maze[x][y] == 'NW':
    
18.             route = [[-1,-1], [0,-1], [-1,0]]
    
19.         elif maze[x][y] == 'SE':
    
20.             route = [[1,1], [0,1], [1,0]]
    
21.         elif maze[x][y] == 'SW':
    
22.             route = [[1,-1], [0,-1], [1,0]]
    
23.             
    
24.         for each in route:
    
25.             node = (path[-1][0] + each[0], path[-1][1] + each[1])
    
26.             if -1 not in node and r != node[0] and c != node[1]:
    
27.                 if len(path) > limit:
    
28.                     return
    
29.                 if node in path:
    
30.                     continue
    
31.                 path.append(node)
    
32.                 solvingmaze(path,dest)
    
33.                 path.pop(-1)
    
34. 
    
35.     solvingmaze( [ (start[0], start[1]) ] , dest)
    
36.     if len(paths) > 0:
    
37.         m = r*c
    
38.         for each in paths:
    
39.             if m > len(each):
    
40.                 m = len(each)
    
41.                 i = paths.index(each)
    
42.         print('The preferred path to {} is:'.format(dest))
    
43.         print(paths[i],len(paths))
    
44.     else:
    
45.         print('There is no path to {}'.format(dest))
    
46.    
    
47. def main():
    
48.     solveMaze((3,3),(0,0))
    
49.     solveMaze((3,3),(0,6))
    
50.     solveMaze((3,3),(6,0))
    
51.     solveMaze((3,3),(6,6))
    
52.    
    
53. main()

复制代码