题解 | #拜访#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型二维数组 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    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;
        }
    }
}