Repository navigation
Expand file tree
/
Copy pathTheMaze.java
More file actions
105 lines (91 loc) · 2.98 KB
/
Copy pathTheMaze.java
File metadata and controls
105 lines (91 loc) · 2.98 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package com.bytetree.lintcode.array;
import java.util.LinkedList;
import java.util.Queue;
/**
* 787. The Maze
* <p>
* There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
* <p>
* Given the ball's start position, the destination and the maze, determine whether the ball could stop at the destination.
* <p>
* The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
* <p>
* 1.There is only one ball and one destination in the maze.
* 2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
* 3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
* 5.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
* <p>
* Example
* Example 1:
* <p>
* Input:
* map =
* [
* [0,0,1,0,0],
* [0,0,0,0,0],
* [0,0,0,1,0],
* [1,1,0,1,1],
* [0,0,0,0,0]
* ]
* start = [0,4]
* end = [3,2]
* Output:
* false
* Example 2:
* <p>
* Input:
* map =
* [[0,0,1,0,0],
* [0,0,0,0,0],
* [0,0,0,1,0],
* [1,1,0,1,1],
* [0,0,0,0,0]
* ]
* start = [0,4]
* end = [4,4]
* Output:
* true
* <p>
* <a href="https://www.lintcode.com/problem/the-maze/description">787. The Maze</a>
* <p>
* Created by vencial on 2019-10-08.
*/
public class TheMaze {
/**
* @param maze: the maze
* @param start: the start
* @param destination: the destination
* @return: whether the ball could stop at the destination
*/
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
// write your code here
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
Queue<Integer> queue = new LinkedList<>();
visited[start[0]][start[1]] = true;
queue.offer(start[0] * n + start[1]);
int[] dirs = {-1, 0, 1, 0, -1};
while (!queue.isEmpty()) {
int curPosition = queue.poll();
for (int i = 0; i < 4; i++) {
int x = curPosition / n;
int y = curPosition % n;
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != 1) {
x += dirs[i];
y += dirs[i + 1];
}
x -= dirs[i];
y -= dirs[i + 1];
if (x == destination[0] && y == destination[1]) {
return true;
}
if (!visited[x][y]) {
visited[x][y] = true;
queue.offer(x * n + y);
}
}
}
return false;
}
}