490. The Maze

bfs O(mn) time O(mn) space
这道题的意思是球一直滚到撞墙才能停下换方向
bfs可以避免不必要的stackoverflow

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        unordered_set<int> s{start[0] * n + start[1]}; // 先放起点去重
        queue<vector<int>> q;
        q.push(start);
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto v = q.front(); q.pop();
            if (v == destination) return true;
            for (int i = 0; i < 4; ++i) {
                int r = v[0], c = v[1];
                while (0 <= r && r < m && 0 <= c && c < n && maze[r][c] == 0) {
                    r += dr[i];
                    c += dc[i];
                }
                r -= dr[i];
                c -= dc[i];
                if (!s.count(r * n + c)) {
                    s.insert(r * n + c);
                    q.push({r, c});
                }
            }
        }
        return false;
    }
};