题解 | #拜访#

拜访

http://www.nowcoder.com/practice/491828fc7d93459db450b344c2aaaeef

题目的主要信息：

现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向或在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。

给定一个地图 CityMap 及它的行长度 n 和列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。

注意：需保证所有方案的距离都是最短的方案

方法一：

层次遍历。把路径看成一颗树，用层次遍历的方法保证路径都是最短。从起始位置出发，枚举四个方向，每次将所有合法的下一层位置放入队列，如果位置已经被访问过则设置为不能访问。 alt 具体做法：

class Solution {
public:

    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        int directions[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};//四个运动方向
        queue<pair<int, int>> q;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j) 
                if(CityMap[i][j] == 1) {//找到地理位置
                    q.push({i, j});
                }
        }
        int res=0;//用于统计方案数量
        while(!q.empty()) {//当队列不为空
            int size = q.size();
            for(int i=0;i<size;i++){
                pair<int,int> pos = q.front();//队列
                q.pop();
                if(CityMap[pos.first][pos.second]==2){//如果访问到了商家，则res++
                    res++;
                    continue;
                }
                CityMap[pos.first][pos.second]=-1;//将当前层设置为已访问
                for(int i=0;i<4;i++){//下一层入队列
                    int x=pos.first+directions[i][0];//下一层的坐标x
                    int y=pos.second+directions[i][1];//下一层的坐标y
                    if(x<0||x>=n||y<0||y>=m||CityMap[x][y]==-1){//如果坐标不合法则换一个方向
                        continue;
                    }else{//坐标合法则将位置入队列，便于后续层次遍历。
                        q.push({x,y});
                    }
                }
            }
            if(res!=0){//如果方案数不为0，说明已经到达商家位置
                break;
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (4^{n})$ ，需要遍历所有可能的路径。
空间复杂度： $O (n)$ ，队列中最多储存所有点的位置。

方法二：

用深度优先搜索。记录当前路径长度len，和已知最短路径长度minlen。首先找到起始位置，然后进行深度优先搜索，如果位置不合法或已经访问过或路径比最短路径minlen长则不必访问；如果可以访问，相应的增加路径长度和设置已访问状态，如果到达商家位置，说明找到了一条路径，如果比minlen短，则更新minlen和重置count，恢复原样并回溯。如果没有到达商家位置，则从四个方向继续进行dfs。

具体做法：

class Solution {
public:
    int row;
    int col;
    vector<vector<int>> visited;//访问记录
    int count=0;//方案数
    int directions[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四个方向
    int x,y;//记录起始位置的坐标
    int len=0;//路径长度
    int minlen=999;//最短路径长度
    void dfs(vector<vector<int> >& CityMap, int x, int y) {
        int n = row, m = col;
        //位置不合法或已经访问过或路径比最短路径长则不必访问
        if(x<0 || x>=n || y<0 || y>=m || CityMap[x][y]==-1 || visited[x][y]==1 || len>=minlen){
            return;
        }
        len++;//可以访问，路径长度加1
        visited[x][y] = 1;//设置为已访问
        if(CityMap[x][y] == 2){//如果这个位置是商家位置，说明找到了一条路径
            if(len < minlen){//如果路径长度比目前已知最短路径长度还短，则更新最短路径长度
                minlen = len;
                count = 1;//重置count
            }
            else if(len == minlen){ //找到一条合法路径
                count++;
            }
            //恢复原样，回溯
            visited[x][y] = 0;
            --len;
            return;
        }
        //四个方向进行dfs
        for(int i = 0; i < 4; ++i){
            int xx = x + directions[i][0];
            int yy = y + directions[i][1];
            dfs(CityMap, xx, yy);
        }
        visited[x][y] = 0; //恢复原样，回溯
        len--;
    }
    
    int countPath(vector<vector<int> >& CityMap, int n, int m) {
        row = n;
        col = m;
        visited.resize(n);
        for(int i = 0; i < n; ++i) {
            visited[i].resize(m);
        }
        for(int i = 0; i < n; ++i) {//找到起始位置
            for(int j = 0; j < m; ++j) {
                if(CityMap[i][j] == 1) {
                    x = i;
                    y = j;
                }
            }
        }
        dfs(CityMap, x, y);//深度优先搜索
        return count;
    }
};

复杂度分析：