BFS1
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
53import java.util.*;
class AmazonTreasureIsland{
public static int treasureIsland(char[][] island) {
if (island == null || island.length == 0) return 0;
int steps = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
boolean[][] visited = new boolean[island.length][island[0].length];
visited[0][0] = true;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// bfs
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] coordinate = queue.poll();
int x = coordinate[0];
int y = coordinate[1];
if (island[x][y] == 'X') return steps;
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < island.length && newY >= 0 && newY < island[0].length &&
island[newX][newY] != 'D' && !visited[newX][newY]) {
queue.add(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
}
steps++;
}
return 0;
}
}
public class MyClass {
public static void main(String[] args) {
char[][] island = new char[][]{
{'O', 'O', 'O', 'O'},
{'D', 'O', 'D', 'O'},
{'O', 'O', 'O', 'O'},
{'X', 'D', 'D', 'O'}
};
int result = AmazonTreasureIsland.treasureIsland(island);
System.out.println(String.format("%s (expect 5)", result));
}
}