题解 | #拜访#

思路:

1. 首先，在 原始地图 当中，找到 经理 和 商家 所在的位置；
2. 通过 广度优先遍历，找到经理到商家的 最短路径。注意: 广度优先遍历，只是用来帮助我们找到 这么一条 最短路径，至于这条最短路径 有多少条，我们目前还不得而知；
3. 找到 最短路径的长度 之后，我们就可以进行 深度优先遍历，找到 所有的 最短路径。

说明:

为什么我们从一开始，不直接使用 广度优先遍历，找到 所有的最短路径? 因为，会超时! 广度优先遍历，它只擅长找 路径数，但是它并不擅长找出 在所有的路径中，最短的! 鉴于该原因，我们从一开始，先使用 广度优先遍历 找到 最短路径的长度，然后，以此来 约束，深度优先遍历。只要在这 规定的长度内，没有到达 商家位置，我们就不再向下搜索。相当于，提前进行 剪枝!!! 剪枝!!! 剪枝!!! 把不可能的结果提前排除，减少了搜索的时间!

总结:

这道题还是挺有意思的，同时用到了 广度优先遍历 和 深度优先遍历。对于这类题目，还是要明确题目的 要求是什么，如果 盲目 套用模板，很容易 超时的。

import java.util.*;

public class Solution {

    public static int ans = 0;

    public static int countPath(int[][] CityMap, int n, int m) {
        int[][] copyMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copyMap[i][j] = CityMap[i][j];
            }
        }
        int[] location = managerAndBusinessmanLocation(CityMap);
        int[][] steps = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
        int[] tmpLocation = new int[]{location[0], location[1]};
        queue.add(tmpLocation);
        CityMap[location[0]][location[1]] = -1;
        while (!queue.isEmpty()) {
            tmpLocation = queue.poll();
            int cx = tmpLocation[0];
            int cy = tmpLocation[1];
            if (cx == location[2] && cy == location[3]) {
                break;
            }
            if (cx - 1 >= 0 && cx - 1 < n && cy >= 0 && cy < m && CityMap[cx - 1][cy] != -1) {
                CityMap[cx - 1][cy] = -1;
                steps[cx - 1][cy] = steps[cx][cy] + 1;
                int[] cuLocation = new int[]{cx - 1, cy};
                queue.add(cuLocation);
            }
            if (cx + 1 >= 0 && cx + 1 < n && cy >= 0 && cy < m && CityMap[cx + 1][cy] != -1) {
                CityMap[cx + 1][cy] = -1;
                steps[cx + 1][cy] = steps[cx][cy] + 1;
                int[] cuLocation = new int[]{cx + 1, cy};
                queue.add(cuLocation);
            }
            if (cx >= 0 && cx < n && cy - 1 >= 0 && cy - 1 < m && CityMap[cx][cy - 1] != -1) {
                CityMap[cx][cy - 1] = -1;
                steps[cx][cy - 1] = steps[cx][cy] + 1;
                int[] cuLocation = new int[]{cx, cy - 1};
                queue.add(cuLocation);
            }
            if (cx >= 0 && cx < n && cy + 1 >= 0 && cy + 1 < m && CityMap[cx][cy + 1] != -1) {
                CityMap[cx][cy + 1] = -1;
                steps[cx][cy + 1] = steps[cx][cy] + 1;
                int[] cuLocation = new int[]{cx, cy + 1};
                queue.add(cuLocation);
            }
        }
        int shortestPath = steps[location[2]][location[3]];
        process(copyMap, location[0], location[1], location[2], location[3], shortestPath);
        return ans;
    }

    // 找到 经理 和 商家 所在的位置
    public static int[] managerAndBusinessmanLocation(int[][] CityMap) {
        int[] location = new int[4];
        for (int i = 0; i < CityMap.length; i++) {
            for (int j = 0; j < CityMap[0].length; j++) {
                if (CityMap[i][j] == 1) { // 经理位置
                    location[0] = i;
                    location[1] = j;
                }
                if (CityMap[i][j] == 2) { // 商家位置
                    location[2] = i;
                    location[3] = j;
                }
            }
        }
        return location;
    }

    public static void process(int[][] map, int cx, int cy, int xe, int ye, int steps) {
        if (cx < 0 || cx >= map.length || cy < 0 || cy >= map[0].length || map[cx][cy] == -1) {
            return;
        }
        if (steps == 0) {
            if (cx == xe && cy == ye) {
                ans++;
            }
            return;
        }
        map[cx][cy] = -1;
        process(map, cx - 1, cy, xe, ye, steps - 1);
        process(map, cx + 1, cy, xe, ye, steps - 1);
        process(map, cx, cy - 1, xe, ye, steps - 1);
        process(map, cx, cy + 1, xe, ye, steps - 1);
        map[cx][cy] = 0;
    }
}