The Maze (Leetcode 490)

这道题是一道很新颖的矩阵搜索题。不同于以往的沿着四个方向依次search，这道题是一道沿着一个方向走到底的题目，而我们所需要考虑的点，也仅仅是那些一直走，直到走不下去的边界点。

所以BFS与DFS都建立在边界点上，只需search这些点，而且沿着四个方向走到底，直到找到destination。

BFS (注意注释的地方):

class Solution {
public:

    bool isValid(int x, int y, vector<vector<int>>& maze){
        if(x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0) return true;
        return false;
    }

    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(maze.empty() || maze[0].empty() || start.empty() || destination.empty()) return 0;
        int row = maze.size(), col = maze[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<pair<int, int>> q;
        q.push({start[0], start[1]});
        visited[start[0]][start[1]] = true;
        
        while(!q.empty()){
            int cur_x = q.front().first, cur_y = q.front().second;
            q.pop();
            for(int i=0; i<4; i++){  //注意这里： 沿着一个方向走到底
                 int next_x = cur_x, next_y = cur_y;
                 while(isValid(next_x + directions[i].first, next_y + directions[i].second, maze)){
                     next_x += directions[i].first;
                     next_y += directions[i].second;
                 }
                 if(next_x == destination[0] && next_y == destination[1]) return true;
                 if(!visited[next_x][next_y]){
                     visited[next_x][next_y] = true;
                     q.push({next_x, next_y});
                 }
            }
        }
        return false;
    }
};

DFS:

class Solution {
public:

    bool isValid(int x, int y, vector<vector<int>>& maze){
        if(x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0) return true;
        return false;
    }
    
    bool dfs(vector<vector<int>>& maze, vector<vector<bool>> &visited, vector<int> cur, vector<int>& destination){
        
        if(cur[0] == destination[0] && cur[1] == destination[1]) return true;
        else if(visited[cur[0]][cur[1]]) return false;
        visited[cur[0]][cur[1]] = true;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(int i=0; i<4; i++){
            int next_x = cur[0], next_y = cur[1];
            while(isValid(next_x + directions[i].first, next_y + directions[i].second, maze)){
                 next_x += directions[i].first;
                 next_y += directions[i].second; 
            }
            if(dfs(maze, visited, {next_x, next_y}, destination)) return true;
        }
        return false;
    }
    
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        if(maze.empty() || maze[0].empty() || start.empty() || destination.empty()) return 0;
        int row = maze.size(), col = maze[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        return dfs(maze, visited, start, destination);
    }
};