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
| import java.util.LinkedList;
class Solution {
public int solution(int[][] maps) {
// Get map size
int mapX = maps.length;
int mapY = maps[0].length;
System.out.printf("mapX:%d, mapY:%d", mapX, mapY);
// Init vars
boolean[][] visitedMap = new boolean[mapX][mapY];
LinkedList<Position> nextQueue = new LinkedList<>();
// Find path
visitedMap[0][0] = true;
nextQueue.offer(new Position(0, 0, 1));
while(nextQueue.size() != 0) {
// Get next position
Position nextPos = nextQueue.poll();
int nextX = nextPos.getX();
int nextY = nextPos.getY();
int nextDepth = nextPos.getDepth();
// Check this position is goal
if (nextX == mapX - 1 && nextY == mapY - 1) {
return nextDepth;
}
// Enqueue next position to visit
if ((nextX+1 < mapX) && (maps[nextX+1][nextY] == 1) && (!visitedMap[nextX+1][nextY])){
visitedMap[nextX+1][nextY] = true;
nextQueue.offer(new Position(nextX+1, nextY, nextDepth+1));
}
if ((nextY+1 < mapY) && (maps[nextX][nextY+1] == 1) && (!visitedMap[nextX][nextY+1])){
visitedMap[nextX][nextY+1] = true;
nextQueue.offer(new Position(nextX, nextY+1, nextDepth+1));
}
if ((nextX-1 >= 0) && (maps[nextX-1][nextY] == 1) && (!visitedMap[nextX-1][nextY])){
visitedMap[nextX-1][nextY] = true;
nextQueue.offer(new Position(nextX-1, nextY, nextDepth+1));
}
if ((nextY-1 >= 0) && (maps[nextX][nextY-1] == 1) && (!visitedMap[nextX][nextY-1])){
visitedMap[nextX][nextY-1] = true;
nextQueue.offer(new Position(nextX, nextY-1, nextDepth+1));
}
}
// Not reachable
return -1;
}
}
class Position {
public int x;
public int y;
public int depth;
public Position(int x, int y, int depth) {
this.x = x;
this.y = y;
this.depth = depth;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getDepth() {
return depth;
}
}
|