AlgorithmStuff/Maze.py at master · HakuG/AlgorithmStuff · 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
import sys

# Given a maze of Monsters and Walls find the shortest path to the end without losing
# lives

class Queue:
    def __init__(self):
        self.items = []

    def empty(self):
        return self.items == []

    def put(self, item):
        self.items.insert(0,item)

    def get(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

class MazeComponent:
    def __init__(self, row, height, lives):

        self.visited = False
        self.distance = 0
        self.row = row
        self.column = height
        self.lives = lives;
    def visit (self):
        visited = True

def main():
    height, width, lives = map(int, raw_input().split())
    MatrixBegin = [[0 for rows in xrange(width)] for col in xrange(height)]
    MatrixEnd = [[[0 for life in xrange(lives)] for rows in xrange(width)] for col in xrange(height)]
    S = (0, 0)
    E = (0, 0)
    for row in range(height):
        MatrixBegin[row] = map(str, raw_input().split())
        for column in range(width):
            for life in range(lives):
                MatrixEnd[row][column][life] = MazeComponent(row, column, life)
                if MatrixBegin[row][column] == 'S':
                    S = (row,column)
                elif MatrixBegin[row][column] == 'E':
                    E = (row, column)
                    MatrixEnd[row][column][life].distance = -1
                elif MatrixBegin[row][column] == 'X':
                    MatrixEnd[row][column][life].visited = True;
    q = Queue()
    MatrixEnd[S[0]][S[1]][lives -1].distance = 0
    q.put(MatrixEnd[S[0]][S[1]][lives - 1])

    #Check all possible values
    while q.empty() == False:
         u = q.get()
         #print (u.row, u.column, u.lives, u.distance)
         if (u.row + 1 <= height - 1 and MatrixEnd[u.row + 1][u.column][u.lives].visited == False):
            MatrixEnd[u.row + 1][u.column][u.lives].visited = True
            if (MatrixBegin[u.row + 1][u.column] == 'M'):
                if (u.lives - 1 >= 0):
                    MatrixEnd[u.row + 1][u.column][u.lives - 1].visited = True
                    MatrixEnd[u.row + 1][u.column][u.lives - 1].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                    q.put(MatrixEnd[u.row + 1][u.column][u.lives - 1])
                    #print("Found Monster when processing at ", u.row, u.column, " with ", u.lives)
            else:
                MatrixEnd[u.row + 1][u.column][u.lives].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                q.put(MatrixEnd[u.row + 1][u.column][u.lives])

         if (u.row - 1 >= 0 and MatrixEnd[u.row - 1][u.column][u.lives].visited == False):
            MatrixEnd[u.row - 1][u.column][u.lives].visited = True
            if (MatrixBegin[u.row - 1][u.column] == 'M'):
                if (u.lives - 1 >= 0):
                    MatrixEnd[u.row - 1][u.column][u.lives - 1].visited = True
                    MatrixEnd[u.row - 1][u.column][u.lives - 1].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                    q.put(MatrixEnd[u.row - 1][u.column][u.lives - 1])
                    #print("Found Monster when processing at ", u.row, u.column, " with ", u.lives)
            else:
                MatrixEnd[u.row - 1][u.column][u.lives].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                q.put(MatrixEnd[u.row - 1][u.column][u.lives])
         if (u.column + 1 <= width -1 and MatrixEnd[u.row][u.column + 1][u.lives].visited == False):
            MatrixEnd[u.row][u.column + 1][u.lives].visited = True
            if (MatrixBegin[u.row][u.column + 1] == 'M'):
                if (u.lives - 1 >= 0):
                    MatrixEnd[u.row][u.column + 1][u.lives - 1].visited = True
                    MatrixEnd[u.row][u.column + 1][u.lives - 1].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                    q.put(MatrixEnd[u.row][u.column + 1][u.lives - 1])
                    #print("Found Monster when processing at ", u.row, u.column, " with ", u.lives)
            else:
                MatrixEnd[u.row][u.column + 1][u.lives].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                q.put(MatrixEnd[u.row][u.column + 1][u.lives])

         if (u.column - 1 >= 0 and MatrixEnd[u.row][u.column - 1][u.lives].visited == False):
            MatrixEnd[u.row][u.column - 1][u.lives].visited = True
            if (MatrixBegin[u.row][u.column - 1] == 'M'):
                if (u.lives - 1 >= 0):
                    MatrixEnd[u.row][u.column - 1][u.lives - 1].visited = True
                    MatrixEnd[u.row][u.column - 1][u.lives - 1].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                    q.put(MatrixEnd[u.row][u.column - 1][u.lives - 1])
                    #print("Found Monster when processing at ", u.row, u.column, " with ", u.lives)
            else:
                MatrixEnd[u.row][u.column - 1][u.lives].distance = MatrixEnd[u.row][u.column][u.lives].distance + 1
                q.put(MatrixEnd[u.row][u.column - 1][u.lives])
    maxi = -1;
    for life in range (lives):
        if (MatrixEnd[E[0]][E[1]][life].distance > maxi):
            maxi = MatrixEnd[E[0]][E[1]][life].distance
    print(maxi)
main();