题解 | #拜访#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param CityMap int整型二维数组
# @param n int整型
# @param m int整型
# @return int整型
#
class Solution:
    def countPath(self, CityMap: List[List[int]], n: int, m: int) -> int:
        def maze(x, y, step, CityMap):
            if x in range(n) and y in range(m) and CityMap[x][y] != -1:
                step += 1
                if res and step > min(res):
                    return
                if CityMap[x][y] == 2:
                    res.append(step)
                elif CityMap[x][y] == 0 or CityMap[x][y] == 1:
                    CityMap[x][y] = 4
                    maze(x + 1, y, step, CityMap)
                    maze(x, y + 1, step, CityMap)
                    maze(x - 1, y, step, CityMap)
                    maze(x, y - 1, step, CityMap)
                    CityMap[x][y] = 0

        for i in range(n):
            for j in range(m):
                if CityMap[i][j] == 1:
                    startx = i
                    starty = j
        res = []
        step = -1
        maze(startx, starty, step, CityMap)
        return(res.count(min(res)))

python递归，加了一个判断当前路径大于已有的最短路径直接换新路径