Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // O(n)
- public class Solution {
- public boolean hasPath(int[][] maze, int[] start, int[] destination) {
- int m = maze.length, n = maze[0].length;
- int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
- Queue<int[]> queue = new LinkedList<int[]>();
- queue.offer(start);
- boolean[][] visited = new boolean[m][n];
- visited[start[0]][start[1]] = true;
- while(!queue.isEmpty()) {
- int[] point = queue.poll();
- for(int[] dir : dirs) {
- int x = point[0] + dir[0], y = point[1] + dir[1];
- while(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
- x += dir[0];
- y += dir[1];
- }
- x -= dir[0];
- y -= dir[1];
- if(visited[x][y]) continue;
- if(x == destination[0] && y == destination[1]) return true;
- visited[x][y] = true;
- queue.offer(new int[]{x, y});
- }
- }
- return false;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement