05 August 2008
水域是0，比0大的是陆地，相邻格子只相差1，让整个地图（二维数组）里有个陆地最高
因为每个点和相邻点的高度差最大为1，所以，我们需要从已知点出发，将高度不断增加，这样就能满足要求。
因为已知点有多个，每一次增加高度，都会产生新的已知点，所以，不能采用深搜，而是要用宽搜。
先从有水的地方开始作为起始点，每一次迭代产生下一次的已知点作为起始点，知道没有下一个可以搜的点。
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
class Solution {
int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
public int[][] highestPeak(int[][] isWater) {
int n = isWater.length;
if(n == 0) return new int[0][0];
int m = isWater[0].length;
// 定义答案数组
int[][] res = new int[n][m];
// 设置初始值
for(int i = 0; i < n; i++) {
Arrays.fill(res[i], -1);
}
// 搜索起点
List<int[]> st = new ArrayList<>();
// 将有水的点作为起始搜索点
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(isWater[i][j] == 1) st.add(new int[]{i, j});
}
}
bfs(res, st, 0);
return res;
}
// 宽搜，参数分别表示地图高度，当前需要标记的点，当前高度
private void bfs(int[][] res, List<int[]> st, int h) {
// 如果当前没有可以标记的点了，说明搜完了
if(st.size() == 0) return;
// 定义下一步要搜的点
List<int[]> next = new ArrayList<>();
// 标记当前的高度
for(int[] p : st) res[p[0]][p[1]] = h;
// 枚举下一步需要搜索的点集
for(int[] p : st) {
// 上下左右四个方向搜索
for(int i = 0; i < 4; i++) {
// 计算一个点的坐标，并判断是否合法
int tx = p[0] + dx[i], ty = p[1] + dy[i];
if(tx < 0 || tx >= res.length || ty < 0 || ty >= res[0].length || res[tx][ty] != -1) continue;
// 标记这个点已经被加入点集了，防止重复加入
res[tx][ty] = -2;
// 将这个点加入点集
next.add(new int[]{tx, ty});
}
}
// 下一次搜索，高度加一
bfs(res, next, h + 1);
}
}