题解 | #拜访#

题目分析

1. 题目给出了我们一个二维数组，其中标为1的位置含义为出发点，标为2的位置的含义为终点，标记为-1的位置含义为不可达点，其他位置数字为0，表示可以经过的点
2. 从出发点到终点，一定有最短的路径长度，题目要求我们返回最短的路径长度的路径方案数。

方法一：DFS深度优先遍历

• 实现思路

  • 我们需要维护一个命名为mp的map结构，表示（当前达到商家的路径长度，该长度对应方案数量）的映射集合，由于map的有序性，最终返回的结果为mp.begin()->second

  • 我们可以用深度优先搜索的思路，从经理所在的位置出发向四个方向进行深度搜索

  • dfs递归函数表示的含义为：

    • 在CityMap中，如果当前遍历的坐标位置(x,y)越界，则直接返回
    • 如果遇到不可达的位置，或者已访问过的节点，或者当前路径已经经过的长度超过最短路径长度，直接返回
    • 如果遇到商家，则在mp中记录（当前达到商家的路径长度，该长度对应方案数量）的映射
    • 其他情况则说明经理还在前往商家的路上，标记本节点已访问，并向四个方向继续dfs递归，在内层dfs返回回退取消标记已访问

  • 最终返回的结果为mp.begin()->second

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型vector<vector<>> 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    map<int, int> mp;                                              // 存储(最短路径长度，方案数)映射，依赖其排序功能，mp.begin()->second时最终的结果
    int dx[4] = {0, 1, -1, 0};
    int dy[4] = {1, 0, 0, -1};
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        // write code here
        vector<vector<int>> visited(n, vector<int>(m, 0));        // 标记已访问节点
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(CityMap[i][j] == 1) {
                    dfs(CityMap, i, j, 0, visited, n, m);         // 找到经理并从经理出发开始dfs探索路径
                }
            }
        }
        return mp.begin()->second;
    }
    
    void dfs(vector<vector<int> >& CityMap, int x, int y, int dist, vector<vector<int>>& visited, int n, int m) {
        if(x < 0 || x >= n || y < 0 || y >= m) {        // 越界处理返回
            return;
        }
        if(CityMap[x][y] == -1 || visited[x][y] || (mp.size() > 0 && dist > mp.begin()->first)) {    // 不可达返回、已访问返回、路径过长返回
            return;
        }
       
        if(CityMap[x][y] == 2) {            // 存储（当前抵达商家路径长度，方案数）映射
            mp[dist] += 1;
        }
        else {
            visited[x][y] = true;
            for(int k = 0; k < 4; k++) {    // 四个方向进行dfs
                dfs(CityMap, x + dx[k], y + dy[k], dist + 1, visited, n, m);
            }
            visited[x][y] = false;
        }
    }
};

复杂度分析

• 时间复杂度：$O(n\times m)O(n\times m)$，根据每个位置看作一个节点，每次连接两个节点看作一条边的思路来讲，深度优先搜索所做的工作是便遍历了所有边两次，即递归一次，回溯一次，因此时间代价是与边的数量有关，在本题的二维图中，边的数量级别是$O(n\times m)O(n\times m)$，所以时间复杂度为$O(n\times m)O(n\times m)$
• 空间复杂度：$O(n\times m)O(n\times m)$，由于递归栈的最深深度可以达到O(n×m)级别，即递归遍历了所有的节点，而且维护的visited二维数组的空间大小也是$O(n\times m)O(n\times m)$级别，因此得出空间复杂度大小

方法二：动态规划

• 实现思路
  • 我们维护一个二维数组dp[n][m]。
  • 假设CityMap[x1][y1]为经理位置，CityMap[x2][y2]为商家位置。dp[i][j]的含义为经理到达CityMap[i][j]位置的最短路径方案数。初始化dp[x1][y1] = 1，最终需要返回的方案数为dp[x2][y2]
  • 因此我们遍历的范围为x1--->x2，y1--->y2即可。
  • 在寻找最短路径方案数时，对于与经理在同一行、同一列的各个位置的情况：

    • 如果同行、同列没有CityMap[i][j]=-1，则当前位置的最短路径方案数直接继承遍历方向过来的上一个位置的方案数（情况①②）

    • 如果同行、同列存在CityMap[i][j]=-1，则标记dp[i][j]=0指代其不可达，但是当遍历到当前可通行位置的前一个位置为-1的情况，则要重新标记dp[i][j] = 1，表示与-1位置相邻的0位置只有一种最短路径到达方案。（情况①②）

      重新标记dp[i][j] = 1的原因：这是因为如果同行、同列上存在与-1位置相邻的0位置的可达点时，想要到达该0位置只有绕过-1一种方案到达0位置最短。

      举例：对于大小为4×4的图，(1,2)=-1,(1,1)=-1,(2,1)=-1，其余位置为0，如果商家在(0,0)，经理从(2,2)出发，则经理如果想要到达(0,2)点，必须经过(2,2)->(2,3)->(1,3)->(0,3)->(0,2)绕过来时最短的路径，而且有且仅有一种方案。

  • 对于与经理不在同一行、同一列的各个位置的情况：
    • 当前可达位置的方案数为相邻两个位置方案数之和
  • 我们以x1,x2和y1,y2的相对位置来确定dx,dy大小，如果x1<x2，则dx=1，表示经理需要向右方向到商家位置，反之为dx=-1，同理可得dy的取值。
  • 动态规划递推方程有如下形式：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param CityMap int整型vector<vector<>> 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        // write code here        
        int x1, x2 ,y1, y2;
        vector<vector<int>> dp(n, vector<int>(m, 0));    // dp数组初始化
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++){
                if(CityMap[i][j] == 1) {                 // 找到经理的位置
                    x1 = i;
                    y1 = j;
                }
                if(CityMap[i][j] == 2) {                 // 找到商家的位置
                    x2 = i;
                    y2 = j;
                }
            }
        }
        int dx = x1 < x2 ? 1 : -1;                       // 确定经理应该前进的方向
        int dy = y1 < y2 ? 1 : -1;
        dp[x1][y1] = 1;                                  // 初始化经理位置为1
        for(int x = x1 + dx; x != x2 + dx; x += dx) {            // 经理纵方向的每个到达位置最短的方案数
            dp[x][y1] = CityMap[x][y1] != -1 ? dp[x-dx][y1] : 0;
            if(dp[x-dx][y1] == 0) dp[x][y1] = 1;				 // 如果当前可通行位置挨着不能经过的地区，则标记到达当前位置的方案数为1
        }
        for(int y = y1 + dy; y != y2 + dy; y += dy) {            // 经理横方向每个到达位置最短的方案数
            dp[x1][y] = CityMap[x1][y] != -1 ? dp[x1][y-dy] : 0;
            if(dp[x1][y-dy] == 0) dp[x1][y] = 1;				 // 如果当前可通行位置挨着不能经过的地区，则标记到达当前位置的方案数为1
        }
        for(int x = x1 + dx; x != x2 + dx; x += dx) {            // 经理根据横纵两个方向的基础值前进，统计方案数
            for(int y = y1 + dy; y != y2 + dy; y += dy) {
                dp[x][y] = CityMap[x][y] != -1 ? dp[x-dx][y] + dp[x][y-dy] : 0;
            }
        }
        
        return dp[x2][y2];                                       // 返回到达目标位置的方案数
    }
};

复杂度分析

• 时间复杂度：$O(n\times m)O(n\times m)$，由于需要遍历二维数组，时间代价为二维的代价
• 空间复杂度：$O(n\times m)O(n\times m)$，由于维护了$dpdp$数组，所以空间代价为二维代价