题解 | #拜访#

题意整理

• 给定一个地图CityMap及它的行长度n和列长度m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区。
• 求从经理位置出发到达商家位置的所有最短路径有多少种。

方法一（广度优先搜索）

1.解题思路

• 首先定义一个队列，用于广度优先搜索。定义一个标记数组，用于标记该位置是否访问过。定义一个距离数组dist，用于记录起点到当前位置的最短距离。定义一个dp数组，用于记录起点到当前位置最短距离的方案数。
• 然后将起点坐标放入队列，并初始化方案数和标记，进行搜索。
• 搜索的过程中，需要往上下左右四个方向进行搜索。如果没有越界，并且不在障碍区，分两种情况进行讨论。一种是没有访问过的点，直接跟新标记数组，距离加1，并且将dp方案数传到当前位置。另一种是访问过的点，如果距离刚好等于前一步加1，说明这个距离已经有方案了，需要加上之前的方案数。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    //方向数组
    int[] dx=new int[]{-1,1,0,0};
    int[] dy=new int[]{0,0,-1,1};
    //用于广度优先搜索
    LinkedList<int[]> queue;
    int[][] CityMap;
    //标记数组
    boolean[][] v;
    //dp[i][j]表示起点到当前位置最短距离的方案数
    int[][] dp;
    //dist[i][j]表示起点到当前位置的最短距离
    int[][] dist;
    public int countPath (int[][] CityMap, int n, int m) {
        //初始化
        this.queue=new LinkedList<>();
        this.CityMap=CityMap;
        this.v=new boolean[n][m];
        this.dp=new int[n][m];
        this.dist=new int[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});
                    dp[i][j]=1;
                    v[i][j]=true;
                    //广度优先搜索
                    bfs();
                    break;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //找到商家位置，返回对应方案数
                if(CityMap[i][j]==2){
                    return dp[i][j];
                }
            }
        }
        return -1;
    }
    
    private void bfs(){
        while(!queue.isEmpty()){
            int[] cur=queue.poll();
            int i=cur[0],j=cur[1];
            int n=CityMap.length,m=CityMap[0].length;
            //往上下左右四个方向搜索
            for(int k=0;k<4;k++){
                int x=i+dx[k];
                int y=j+dy[k];
                //如果没有越界，并且不在障碍区
                if(x>=0&&x<n&&y>=0&&y<m&&CityMap[x][y]!=-1){
                    //未访问过
                    if(!v[x][y]){
                        v[x][y]=true;
                        //距离加1
                        dist[x][y]=dist[i][j]+1;
                        //由于未访问过，对应方案数不变
                        dp[x][y]=dp[i][j];
                        queue.offer(new int[]{x,y});
                    }
                    else{
                        //如果刚好是同样最短距离的路径（广度优先，距离总是由小到大）
                        if(dist[x][y]==dist[i][j]+1){
                            //加上之前方案数
                            dp[x][y]+=dp[i][j];
                        }
                    }
                    
                }
            }
        }
    }
    
}

3.复杂度分析

• 时间复杂度：需要遍历地图上所有的位置，所以时间复杂度是$O(n\ast m)O(n*m)$。
• 空间复杂度：需要额外大小为$n\ast mn*m$的队列、标记数组、dist数组、dp数组，所以空间复杂度为$O(n\ast m)O(n*m)$。

方法二（深度优先搜索）

1.解题思路

• 首先新建一个TreeMap，key存储路径距离，value存储对应的方案数。
• 然后找到经理的位置，进行深度优先搜索。如果遇到越界、遇到障碍物、已经访问过、或者距离更大的情况，直接返回。如果找到一条合法路径，则加入到map。
• 每次更新标记数组，并往四个方向进行深度优先搜索。每次搜索完，可重置标记数组进行回溯。
• 最后map的第一个key对应的是最短的路径距离，返回对应的value即可。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    //新建map，key存储路径距离，value存储对应的方案数
    TreeMap<Integer,Integer> map=new TreeMap<>();
    //方向数组
    int[] dx=new int[]{-1,1,0,0};
    int[] dy=new int[]{0,0,-1,1};
    public int countPath (int[][] CityMap, int n, int m) {
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //找到经理位置，并进行深度优先搜索
                if(CityMap[i][j]==1){
                    dfs(CityMap,i,j,0,new boolean[n][m]);
                    break;
                }
            }
        }
        //返回map中第一个entry的值，也就是最短距离的方案数
        return map.firstEntry().getValue();
    }
    
    private void dfs(int[][] CityMap,int i,int j,int dist,boolean[][] v){
        int n=CityMap.length,m=CityMap[0].length;
        //越界、遇到障碍物、已经访问过、或者距离更大的情况，直接返回
        if(i<0||i>=n||j<0||j>=m||CityMap[i][j]==-1||v[i][j]||(map.size()>0&&dist>map.firstKey())){
            return;
        }
        //找到一条合法路径，加入到map
        if(CityMap[i][j]==2){
            map.put(dist,map.getOrDefault(dist,0)+1);
        }
        else{
            //更新标记数组
            v[i][j]=true;
            //往四个方向进行深度优先搜索
            for(int k=0;k<4;k++){
                dfs(CityMap,i+dx[k],j+dy[k],dist+1,v);
            }
            //回溯，将标记数组还原
            v[i][j]=false;
        }
    }
    
}

3.复杂度分析

• 时间复杂度：需要遍历地图上所有的位置，所以时间复杂度是$O(n\ast m)O(n*m)$。
• 空间复杂度：起点到终点的最短距离不会超过$n\ast mn*m$（覆盖整个地图），所以map所能存储的合法key最多有$n\ast mn*m$个，即需要额外大小为$n\ast mn*m$的map。另外，最坏情况下，递归栈的深度为$m+nm+n$，所以空间复杂度为$O(n\ast m)O(n*m)$。