The Maze

class Point {
    int x, y;
    public Point(int _x, int _y){
        x = _x;
        y = _y;
    }
}
public boolean hasPath(int[][] maze, int[] start, int[] destination){
    int rows = maze.length;
    int cols = maze[0].length;
    if(start[0] == destination[0] && start[1] == destination[1]){
        return true;
    }
    int[][] direct = int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    boolean[][] visited = new boolean[rows][cols];
    Queue<Point> queue = new LinkedList<>();
    visited[start[0]][start[1]] = true;
    queue.offer(new Point(start[0], start[1]));
    while(!queue.isEmpty()){
        Point p = queue.poll();
        int x = p.x;
        int y = p.y;
        for(int i = 0; i i < direct.length; i++){
            int new_x = x, new_y = y;
            while(new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && maze[new_x][new_y] == 0){
                new_x += direct[i][0];
                new_y += direct[i][1];
            }
            new_x -= direct[i][0];
            new_y -= direct[i][1];
            if(visited[new_x][new_y]){
                continue;
            }
            visited[new_x][new_y] = true;
            if(destination[0] == new_x && destination[1] == new_y){
                return true;
            }
            queue.offer(new Point(new_x, new_y));
        }
    }
    return false;
}

[LeetCode] The Maze

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s