Practice_of_Python-Coursera/Maze Problem.py at master · Datoto1205/Practice_of_Python-Coursera · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# Maze Problem (applied the idea of stack)
maze = [[0,0,1,1,1,1,1,1,1,1],
[1,0,0,0,1,0,0,0,1,1],
[1,0,1,1,0,0,1,0,1,1],
[1,0,0,0,0,1,0,0,0,1],
[1,1,0,1,0,1,0,1,0,1],
[1,1,1,1,1,1,0,1,1,1],
[1,0,0,0,0,0,0,1,0,0],
[1,1,0,1,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]]
# We assume that the the most top left one is the origin of the corordinate, 1 means wakk, and 0 means road.
# We assume that the extrance of this maze was on the top & left side.

correctRoute = []   # It involved all the point of the correct route.
routeHistory = []   # It involved all the point we went through so that we could use it to force the computer to change the direction if we entered the blind alley.

def findTheStart(maze):
    for i in range(0, len(maze)):
        if (maze[i][0] == 0):
            correctRoute.append([i, 0])
            break
# We use this function to find the extrance of the maze.

findTheStart(maze)

# Afterward, we devided our movement into four parts with the direction.
def goUp():

    location = correctRoute[len(correctRoute)-1]
    movedLocation = [location[0]-1, location[1]]

    if (location[0] == 0):
        return False
        # Go out of the maze.

    if (maze[location[0]-1][location[1]] == 1):
        return False
        # Face the wall.

    if (movedLocation in routeHistory):
        return False
        # To prevent the problem of blind alley.
        # We could use syntax "a in b" to examine whether a is in b.
    else:
        correctRoute.append(movedLocation)
        routeHistory.append(movedLocation)
        return True

def goRight():

    location = correctRoute[len(correctRoute)-1]
    movedLocation = [location[0], location[1]+1]

    if (location[1] == 11):
        return False
    elif (maze[location[0]][location[1]+1] == 1):
        return False
    elif (movedLocation in routeHistory):
        return False
    else:
        correctRoute.append(movedLocation)
        routeHistory.append(movedLocation)
        return True

def goDown():

    location = correctRoute[len(correctRoute)-1]
    movedLocation = [location[0]+1, location[1]]

    if (location[0] == 11):
        return False
    elif (maze[location[0]+1][location[1]] == 1):
        return False
    elif (movedLocation in routeHistory):
        return False
    else:
        correctRoute.append(movedLocation)
        routeHistory.append(movedLocation)
        return True

def goLeft():

    location = correctRoute[len(correctRoute)-1]
    movedLocation = [location[0], location[1]-1]

    if (location[1] == 0):
        return False
    elif (maze[location[0]][location[1]-1] == 1):
        return False
    elif (movedLocation in routeHistory):
        return False
    else:
        correctRoute.append(movedLocation)
        routeHistory.append(movedLocation)
        return True

def exploring():
    location = correctRoute[len(correctRoute)-1]

    if (goUp() == False):   # When we check whether it is false, it seems that python would run this code of line automatically.
        if (goDown() == False):
            if (goRight() == False):
                if (goLeft() == False):
                    correctRoute.pop()  # To prevent the problem of blind alley.

    correctRouteLocationX = correctRoute[len(correctRoute)-1]   # Latest location
    if (correctRouteLocationX[1] < 9):  # If you did not find the exit which located on the right & bottom side of the maze, keep searching it.
        exploring()


exploring()
print("The the ordinates of each point in the route were shown below:")
print(correctRoute)