AM 787. The Maze

Code(Language:C++) (Judger:ip-172-31-12-4)

class Solution {
public:
    /**
     * @param maze: the maze
     * @param start: the start
     * @param destination: the destination
     * @return: whether the ball could stop at the destination
     */
    struct node{
        int x, y;
        node(int x, int y){
            this->x = x; 
            this->y = y; 
        }
    };  
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1}; 
    const int dir = 4; 
    
    bool canStop(int x, int y, vector<vector<int>> &maze){
        if(x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1){
            return true;
        }
        return false; 
    }

    bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) {
        // write your code here
        // 带有条件的，在matrix中找路径。只有在停下来时才能选择方向。
        // 放入queue里的都是能停下来的点。
        // 其他和普通BFS找路径没啥区别。
        const int m = maze.size();
        if(m == 0){
            return false; 
        }
        const int n = maze[0].size();
        std::queue<node> q;
        q.push(node(start[0], start[1]));
        maze[start[0]][start[1]] = 2; 
        while(!q.empty()){
            node tmp = q.front();
            q.pop();
            if(tmp.x == destination[0] && tmp.y == destination[1]){
                return true; 
            }
            for(int i = 0; i < dir; i++){
                int newX = tmp.x + dx[i];
                int newY = tmp.y + dy[i]; 
                while(!canStop(newX, newY, maze)){
                    newX += dx[i];
                    newY += dy[i]; 
                }
                newX -= dx[i];
                newY -= dy[i]; 
                if(maze[newX][newY] == 2){
                    continue; 
                }
                maze[newX][newY] = 2; 
                q.push(node(newX, newY)); 
            }
        }
        return false; 
    }
};