题解 | #拜访#

这是一道BFS + DP的问题

首先计算最短路径一般都是使用BFS，这道题的难点是不但要计算出最短的长度还需要知道有多少条这样的最短路径 那么我们假设 到达 $i,j-1i\; ,\; j-1$的有$dp[i][j-1]dp[i][j-1]$种方案，到达 $i-1,ji-1,j$有$dp[i-1][j]dp[i-1][j]$ 方案，从这两点都能去i,j,那么有

$dp[i][j]=dp[i][j-1]+dp[i-1][j]dp[i][j]\; =\; dp[i][j-1]\; +\; dp[i-1][j]$

因为本题有最多四个方向可以转移，所以需要最多四次

但是怎样保证每次转移得到的一定是最短的路径呢。这就需要维护一个dist数组来保证到达i,j点一定是最短路，可以明确的是，因为我们采用的是bfs，bfs可以保证首次可以到达的点一定是最短的，那么如果某个点不是第一次到达的，那只需要判断，当前维护的dist，是否等于从转移的点+1，如果是，那么说明这条转移是合理的，需要dp转移，否则是无效的，因为大于当前维护的最短路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param CityMap int整型二维数组 
# @param n int整型 
# @param m int整型 
# @return int整型
#
import collections
class Solution:
    def countPath(self , CityMap: List[List[int]], n: int, m: int) -> int:
        # write code here
        q = collections.deque()
        dist = [[0] * m for _ in range(n)]
        visit = [[False] * m for _ in range(n)]
        dp = [[0] * m for _ in range(n)]
        def bfs(i,j):
            q.append((i,j))
            dp[i][j] = 1
            while len(q) > 0:
                x , y = q.popleft()
                for idx,idy in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nx = idx + x 
                    ny = idy + y 
                    if 0 <= nx < n and 0 <= ny < m and CityMap[nx][ny] != -1:
                        if visit[nx][ny] == False:
                            q.append((nx,ny))
                            visit[nx][ny] = True
                            dist[nx][ny] = dist[x][y] + 1
                            dp[nx][ny] = dp[x][y]
                        else:
                            if dist[nx][ny] == dist[x][y] + 1:
                                dp[nx][ny] += dp[x][y]
               
        for i in range(n):
            for j in range(m):
                if CityMap[i][j] == 1:
                    bfs(i,j)
                    break
        for i in range(n):
            for j in range(m):
                if CityMap[i][j] == 2:
                    return dp[i][j]
        return 0