05 August 2008
跟490 I和505 II 比起来，需要把最短的路径打出来
同II的解法， BFS
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
class Point implements Comparable<Point> {
int dist; // distance from ball
int row;
int col;
String dir; // directions from ball
Point(int dist, int row, int col, String dir) {
this.dist = dist;
this.row = row;
this.col = col;
this.dir = dir;
}
public int compareTo(Point other) {
return this.dist == other.dist ? this.dir.compareTo(other.dir) : this.dist - other.dist;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
boolean[][] visited = new boolean[maze.length][maze[0].length];
PriorityQueue<Point> pq = new PriorityQueue<>();
pq.offer(new Point(0, ball[0], ball[1], ""));
// arrays used for exploring 4 directions from a point
char[] dstr = {'d', 'l', 'r', 'u'};
int[][] dirs = { {1,0},{0,-1},{0,1},{-1,0} };
while (!pq.isEmpty()) {
Point pt = pq.poll();
if (pt.row == hole[0] && pt.col == hole[1]) {
return pt.dir;
}
visited[pt.row][pt.col] = true;
for (int i = 0; i < dirs.length; i++) {
int newRow = pt.row;
int newCol = pt.col;
int dist = pt.dist;
String ds = pt.dir;
// Explore current direction until hitting a wall or the hole
while (newRow + dirs[i][0] >= 0 &&
newRow + dirs[i][0] < maze.length &&
newCol + dirs[i][1] >= 0 &&
newCol + dirs[i][1] < maze[0].length &&
maze[newRow + dirs[i][0]][newCol + dirs[i][1]] != 1) {
newRow += dirs[i][0];
newCol += dirs[i][1];
dist += 1;
if (newRow == hole[0] && newCol == hole[1]) {
break;
}
}
if (!visited[newRow][newCol]) {
pq.offer(new Point(dist, newRow, newCol, ds+dstr[i]));
}
}
}
return "impossible";
}