490. The Maze (spfa

T: O(mn)
S: O(mn)

class Solution {
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        visited[start[0]][start[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == destination[0] && cur[1] == destination[1]) {
                return true;
            }
            for (int[] dir : dirs) {
                int x = cur[0];
                int y = cur[1];
                // ticky, notice, if don't use like this, it will out of bound
                while (isValid(maze, x+dir[0], y+dir[1])) { 
                    x += dir[0];
                    y += dir[1];
                }
                if (!visited[x][y]) {
                    queue.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }
        return false;
    }
    private boolean isValid(int[][] maze, int x, int y) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length 
            && maze[x][y] == 0;
    }
}

/*
know start, end

try bfs to reach dest (SPFA, use a while, this is a complex graph)

can rolling up, down, left or right until hit wall

maze is the obs

T: O(mn)
S: O(mn)
*/