5 Cheese in Maze

Tom is chasing jerry in a maze. He needs to eat all Cheeses in the maze, then only then he will be able to reach Jerry. You have to find smallest path that TOM should take to eat all Cheeses and reach Jerry. TOM can only run straight – left, right, top and down. Input : Tom Position (0,0) Jerry Position (3,3) we use 2 to represent cheese in maze, 1 represent wall.

matrix = [
        [T,0,1,1],
        [2,0,0,1],
        [2,0,0,0],
        [2,2,2,J]
        ]

思路：暴力DFS就可以了。DFS的中止条件是，走到了jerry那里并且吃光了所有cheese。

不过我们可以通过剪枝来优化。因为我们最后需要输出的steps,所以如果我们存当前最小的steps，只要超过这个steps我们就没必要再往下dfs了。需要注意的是，因为路径可以重复走（因为有可能cheese在一条死路里，必须原路返回），所以我们要用一个set来存已经吃过的cheese，再走到这个cheese的时候我们就不+1 cheese了。

class Solution(object):
    def mazeGame(self, start, end, matrix):

        # count how many cheese in maze
        cnt = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==2:
                    cnt += 1
        # dfs
        self.res = float('Inf')
        self.dfs(start[0], start[1], matrix, end, 0, [], cnt)
        return self.res

    def dfs(self, i, j, matrix, end, step, cheese, cnt):
        if [i, j]==end and len(cheese)==cnt:
            self.res = min(self.res, step)
            return

        # if step is larger tham current min exit
        if step>min(self.res, 50):
            return

        if matrix[i][j]==2 and (i,j) not in cheese:
            new_cheese = cheese+[(i,j)]
        else:
            new_cheese = cheese[:]

        for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
            m, n = i+dp[0], j+dp[1]
            if 0<=m<len(matrix) and 0<=n<len(matrix[0]) and matrix[m][n]!=1:
                self.dfs(m, n, matrix, end, step+1, new_cheese, cnt)

matrix = [
        [0,0,1,1],
        [2,0,0,1],
        [2,0,0,0],
        [2,2,2,0]
        ]
start, end = [0,0], [3,3]
so = Solution()
ans = so.mazeGame(start, end, matrix)
print ans