490. The Maze

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return bfsHelper(maze, start, destination, visited);
    }
    
    private boolean bfsHelper(int[][] maze, int[] start, int[] destination, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        int[][] dirs = `{`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`}`;
        queue.offer(start);
        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] + dir[0];
                int y = cur[1] + dir[1];
                while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                }
                if (! visited[x - dir[0]][y - dir[1]]) {
                    queue.add(new int[]{x - dir[0], y - dir[1]});
                }
                visited[x - dir[0]][y - dir[1]] = true;
            }
        }
        return false;
    }
}

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfsHelper(maze, start, destination, visited);
    }
    
    private boolean dfsHelper(int[][] maze, int[] cur, int[] destination, boolean[][] visited) {
        if (visited[cur[0]][cur[1]]) {
            return false;
        }
        if (destination[0] == cur[0] && destination[1] == cur[1]) {
            return true;
        }
        visited[cur[0]][cur[1]] = true;
        int[][] dirs = `{`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`}`;
        for (int[] dir : dirs) {
            int x = cur[0] + dir[0];
            int y = cur[1] + dir[1];
            while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                x += dir[0];
                y += dir[1];
            }
            if (dfsHelper(maze, new int[]{x - dir[0], y - dir[1]}, destination, visited)) {
                return true;
            }
        }
        return false;
    }
}