题目主要信息

1、给一个矩阵，其中1表示起点，2表示终点，-1代表不可经过，0代表可以经过

2、找出找出所有合法路径，并且所有路径均为最短路径

方法一:层次遍历

具体方法

一般来说，在矩阵中，如果涉及到最短路径，BFS是通用做法，但是在本题中，因为最短路径不止一条，且必须要找到所有最短路径，因此我们可以采用层次遍历的方式，同时不剔除重复点的方式，通过统计终点被遍历的次数来确认最短路径的个数。具体如图所示

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int[][] directions = new int[][]{{1,0}, {-1, 0}, {0,1}, {0, -1}};
    public int countPath (int[][] CityMap, int n, int m) {
        // write code here
        int ans = 0;
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(CityMap[i][j]==1){  //找到起点
                    queue.offer(new int[]{i,j});
                }
            }
        }
        while(!queue.isEmpty()){
            for(int i=queue.size(); i>0; i--){  //层次遍历
                int[] p = queue.poll();
                int x = p[0], y = p[1];
                if(CityMap[x][y]==2){
                    ans++;
                    continue;
                }
                CityMap[x][y] = -1;  //代表本层已访问
                for(int[] direction : directions){
                    int newx = x + direction[0];
                    int newy = y + direction[1];
                    if(newx>=n || newx<0 || newy<0 || newy>=m || CityMap[newx][newy]==-1){  //排除不可达
                        continue;
                    }else{
                        queue.offer(new int[]{newx, newy});
                    }
                }
            }
            if(ans!=0){
                break;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(4^n)O(4^n)$,所有可能路径个数
• 空间复杂度：$O(4^n)O(4^n)$，队列中储存的所有点的最大值

方法二：BFS+DP

具体方法

在方法一中，我们通过不剔除重复点的方法，来进行统计路径总数，这使得时间复杂度较高。

这里我们可以通过设计一个dp数组，记录到达每个点处的最短路径的条数，则不需要重复访问多个点。

为了确认是否为最短路径，还需要设计dist数组，来记录到达每个点的最短路径。

最后设计visited数组，来记录每个点是否已经被加入访问队列。

具体设计见代码。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int[][] directions = new int[][]{{1,0}, {-1, 0}, {0,1}, {0, -1}};
    public int countPath (int[][] CityMap, int n, int m) {
        // write code here
        int ans = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[][] dist = new int[n][m];
        int[][] dp = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(CityMap[i][j]==1){ //确认出发点
                    queue.offer(new int[]{i,j});
                    dist[i][j] = 1;  //出发点距离为1
                    dp[i][j] = 1;  //出发点的最短路径数为1
                }
            }
        }
        while(!queue.isEmpty()){
            int[] p = queue.poll();
            int x = p[0], y = p[1];
            if(CityMap[x][y]==2){
                return dp[x][y];
            }
            CityMap[x][y] = -1;
            for(int[] direction : directions){
                int newx = x + direction[0];
                int newy = y + direction[1];
                if(newx>=n || newx<0 || newy<0 || newy>=m || CityMap[newx][newy]==-1){  //判断不可达
                    continue;
                }
                if(dist[newx][newy]==0 || dist[newx][newy]==dist[x][y]+1){  //dist[newx][newy]为0或当前访问点加1，则说明可以通过当前访问点到达目标点，且为最短路径
                    dp[newx][newy] += dp[x][y];  
                    dist[newx][newy] = dist[x][y] + 1;
                }
                
                if(!visited[newx][newy]){  //通过visited数组防止重复加入访问队列
                    queue.offer(new int[]{newx, newy});
                    visited[newx][newy] = true;
                }
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：$O(mn)O(mn)$，每个点都被访问一次
• 空间复杂度：$O(mn)O(mn)$，dp数组、visited数组、dist数组大小