The Maze II (Leetcode 505)

这道题与Maze I 大同小异，不同的是需要search出最短距离。而处理方法也是不同于maze I的 visited数组，在这里采用distance数组来track每个边界点到起点的最短距离。同时当该点距离需要更新时，才做进一步的搜索。

BFS:

class Solution {
public:

    bool isValid(vector<vector<int>>& maze, int x, int y){
        if(x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0) return true;
        return false;
    }
    
    int compute(int x1, int y1, int x2, int y2){
         return abs(x1-x2) + abs(y1-y2);
    }

    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(maze.empty() || maze[0].empty() || start.empty() || destination.empty()) return -1;
        int row = maze.size(), col = maze[0].size();
        vector<vector<int>> distance(row, vector<int>(col, INT_MAX));
        distance[start[0]][start[1]] = 0;
        queue<pair<int, int>> q;
        q.push({start[0], start[1]});
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(!q.empty()){
            int i = q.front().first, j = q.front().second; 
            q.pop();
            for(auto it : directions){
                int x = i, y = j;
                while(isValid(maze, x + it.first, y + it.second)){
                    x += it.first; y += it.second;
                }
                if(distance[x][y] > distance[i][j] + compute(x, y, i, j)){
                    distance[x][y] = distance[i][j] + compute(x, y, i, j);
                    q.push({x, y});
                }
            }
        }
        return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];
    }
};

DFS:

class Solution {
public:

    bool isValid(vector<vector<int>>& maze, int x, int y){
        if(x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0) return true;
        return false;
    }
    
    int compute(int x1, int y1, int x2, int y2){
         return abs(x1-x2) + abs(y1-y2);
    }
    
    void dfs(vector<vector<int>>& maze, vector<vector<int>> &distance, int i, int j){
        int row = maze.size(), col = maze[0].size();
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(auto it : directions){
            int x = i, y = j;
            while(isValid(maze, x + it.first, y + it.second)){
                x += it.first; y += it.second;
            }
            if(distance[x][y] > distance[i][j] + compute(x, y, i, j)){
                distance[x][y] = distance[i][j] + compute(x, y, i, j);
                dfs(maze, distance, x, y);
            }
        }
    }
    
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(maze.empty() || maze[0].empty() || start.empty() || destination.empty()) return -1;
        int row = maze.size(), col = maze[0].size();
        vector<vector<int>> distance(row, vector<int>(col, INT_MAX));
        distance[start[0]][start[1]] = 0;
        dfs(maze, distance, start[0], start[1]);
        return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];
    }
};