爬虫递归解决二维数组迷宫问题

fbsfbsdb

python maze solving answer (Recursion)

talk is cheap show me the code！

1. #import part
   
2. import time
   
3. import sys
   
4. import os
   
5. 
   
6. #global values
   
7. load = 0                                 # set initial loading value
   
8. walk = [(1,0),(-1,0),(0,1),(0,-1)]       # set movements
   
9. backtracker = []                         # set backtracker (remember that this is a stack)
   
10. gmainmaze = []                           # set initial blank maze
    
11. 
    
12. def initialize():   #loading
    
13.     sx = 0 # start x value
    
14.     sy = 0 # start y value
    
15.     ex = 0 # end x value
    
16.     ey = 0 # end y value
    
17.     while load == 0:    #just some cool animation
    
18.         sys.stdout.write("\rloading |")
    
19.         time.sleep(0.1)
    
20.         sys.stdout.write("\rloading /")
    
21.         time.sleep(0.1)
    
22.         sys.stdout.write("\rloading -")
    
23.         time.sleep(0.1)
    
24.         sys.stdout.write("\rloading \")
    
25.         time.sleep(0.1)
    
26.         sys.stdout.write("\r")
    
27.         mainmaze = loadMaze("maze.txt") # IMPORTANT: load the maze under the same folder named "maze.txt"
    
28.         print("Maze Loaded")
    
29.         print(" ")
    
30.         time.sleep(1)
    
31.         print(" ")
    
32.         print("Locating start point...")
    
33.         sx, sy = spotter(5,mainmaze)
    
34.         time.sleep(1)
    
35.         print(" ")
    
36.         print("Locating end point...")
    
37.         ex, ey = spotter(3,mainmaze)
    
38.         print(" ")
    
39.         time.sleep(1)
    
40.         return sx, sy, ex, ey, mainmaze;
    
41.         break
    
42.     print(" ")
    
43.     sys.stdout.write("\rInitialized!")
    
44.     print(" ")
    
45.     time.sleep(3)
    
46.     os.system("cls")
    
47. 
    
48. def loadMaze(filename):
    
49.     #load the data from the file into a 2D list
    
50.     with open(filename) as i:
    
51.         maze = []
    
52.         for line in i:
    
53.             line = line.strip()
    
54.             spawnmaze = line.split(", ")
    
55.             maze.append(spawnmaze)
    
56.     return maze
    
57. 
    
58. def spotter(num,maze):
    
59.     #Locate the 'element' in the maze (this can either be "5" or "3")
    
60.     num = str(num)
    
61.     rowcounter = -1
    
62.     linecounter = 0
    
63.     for rows in maze:
    
64.         rowcounter = rowcounter + 1
    
65.         if num in rows:
    
66.             for element in rows:
    
67.                 if element == num:
    
68.                     print("Tango Spotted, Grid:", rowcounter, linecounter)
    
69.                     return rowcounter, linecounter;
    
70.                     break
    
71.                 linecounter = linecounter + 1
    
72. 
    
73. def valid(maze,x,y): # check if valid
    
74.     height = len(maze) - 1
    
75.     width = len(maze[0]) - 1
    
76.     if 0 <= x <= height and 0 <= y <= width:
    
77.         return 1
    
78.     else:
    
79.         return 0
    
80. 
    
81. def solveMaze(sx,sy,ex,ey): # solve maze
    
82.     global gmainmaze
    
83.     for i in walk:          #try every direction
    
84.         x = sx + i[0]       #make the move
    
85.         y = sy + i[1]
    
86.         if valid(gmainmaze,x,y): # check if still in the maze
    
87.             if x == ex and y == ey: #check if reached destination
    
88.                 print("SITREP:Destination Arrived")
    
89.                 print("The Logistic Path Is:\n",backtracker)
    
90.                 print(" ")
    
91.                 return 1
    
92.             else:
    
93.                 if gmainmaze[x][y] == "0" and (x,y) not in backtracker: #add to the stack
    
94.                     backtracker.append((x,y))
    
95.                 else:
    
96.                     continue
    
97.         else:
    
98.             continue
    
99.         if solveMaze(x,y,ex,ey) == 1: # Recursion (do the next step)
    
100.             return 1
     
101.         else:
     
102.             continue
     
103.     go = backtracker.pop(-1) #moveback while
     
104.     return 0
     
105. 
     
106. def printMaze(maze):
     
107.     for x in range(len(maze)):
     
108.         for y in range(len(maze[x])):
     
109.             print(maze[x][y], end=' ')
     
110.         print("")
     
111. 
     
112. def visualize(maze):    # a cool function to visualize the maze
     
113.     for x in range(len(maze)):
     
114.         for y in range(len(maze[x])):
     
115.             if maze[x][y] == "5":
     
116.                 maze[x][y] = "╳"    # path
     
117.             elif maze[x][y] == "0":
     
118.                 maze[x][y] = "&#9617;"    # unbeen path
     
119.             elif maze[x][y] == "1":
     
120.                 maze[x][y] = "█"    # wall
     
121.             elif maze[x][y] == "3":
     
122.                 maze[x][y] = "╳"    # basically path as well
     
123.             print(maze[x][y], end=' ')
     
124.         print("")
     
125. 
     
126.      
     
127. def main():
     
128.     #initialize the maze
     
129.     sx, sy, ex, ey, mainmaze = initialize()
     
130.     global gmainmaze
     
131.     gmainmaze = mainmaze
     
132.     load = 1
     
133.     #solve the maze
     
134.     gmainmaze[sx][sy] = "0"
     
135.     gmainmaze[ex][ey] = "0" # change the start and end into "0" to make it a way
     
136.     solveMaze(sx,sy,ex,ey)
     
137.     for i in backtracker:
     
138.         gmainmaze[i[0]][i[1]] = "5"
     
139.     gmainmaze[sx][sy] = "5"
     
140.     gmainmaze[ex][ey] = "3" # change the start and end back
     
141.     #print the maze
     
142.     width = len(gmainmaze[0]) - 1
     
143.     print("Check Your Map...")
     
144.     print("Map:")
     
145.     print("--"*(width+1))
     
146.     printMaze(gmainmaze)
     
147.     print("--"*(width+1))
     
148.     #visualize the maze uncomment to establish the function (btw check if your terminal can print these unicodes)
     
149.     #visualize(gmainmaze)
     
150.     time.sleep(5)
     
151. 
     
152. main()
     

复制代码

迷宫长这样：
0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 1, 1, 0, 1, 1, 1, 0
0, 1, 0, 0, 0, 0, 0, 1, 0
0, 1, 0, 1, 1, 1, 0, 0, 0
0, 0, 0, 1, 1, 3, 0, 1, 0
0, 1, 0, 0, 0, 0, 0, 1, 0
0, 1, 1, 1, 0, 1, 1, 1, 0
0, 0, 0, 0, 0, 0, 0, 0, 5        


结果：
&#9617; &#9617; &#9617; &#9617; &#9617; &#9617; &#9617; &#9617; &#9617;
&#9617; █ █ █ &#9617; █ █ █ &#9617;
&#9617; █ &#9617; &#9617; &#9617; &#9617; &#9617; █ &#9617;
&#9617; █ &#9617; █ █ █ &#9617; &#9617; &#9617;
&#9617; &#9617; &#9617; █ █ ╳ &#9617; █ &#9617;
&#9617; █ &#9617; &#9617; ╳ ╳ &#9617; █ &#9617;
&#9617; █ █ █ ╳ █ █ █ ╳
&#9617; &#9617; &#9617; &#9617; ╳ ╳ ╳ ╳ ╳

github(自古以来那些看ph站的看不起我们这些看gh站的):https://github.com/JK88-1337/MazeSolve