给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围
问题
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围.
输入:
11110
11010
11000
00000
输出: 1
输入:
11000
11000
00100
00011
输出: 3
思考
由题意可知: 如果二维网格中的一系列 1 是连续不间断的, 则说明他们是一个岛屿. 所以可以计数一个 1 节点能到达的所有节点, 能到达的 1 节点都属于同一个岛屿, 在查找路径过程中如果遇到了 0 则代表走到了岛屿边界, 结束该节点的路径查找, 继续找下一个没有被访问过 1 节点作为查找的起点.
综上, 可使用 BFS 思想, 以一个 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
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
|
class Solution {
// 从每个节点开始 BFS 遍历, 直到遇到 0 结束. BFS 会遍历完与一个节点相连的所有节点, 同时要保证一个节点只会被访问1次(通过将节点记为 0 表示已经访问过)
public int numIslands(char[][] grid) {
if(grid==null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int count = 0;
// 上下左右邻居与当前节点的索引的差值
int[][] neiber = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for(int i=0; i< m; i++) {
for (int j=0; j<grid[i].length; j++) {
// 遇到 0 节点不用访问
if(grid[i][j] == '0'){
continue;
}
count ++;
Deque<Integer> que = new ArrayDeque();
que.add(i*n+j);
while(!que.isEmpty()) {
int cur = que.pop();
int row = cur/n;
int column = cur%n;
// System.out.println("v:" + row+","+ column);
// 代替下面注释的添加邻居的代码
for(int k=0; k< neiber.length; k++){
int r = neiber[k][0] + row;
int col = neiber[k][1] + column;
if(r > -1 && r < grid.length && col > -1 && col < grid[row].length && grid[r][col] != '0') {
que.add(r*n+col);
grid[r][col] = '0'; // 标记为已访问, 避免重复添加
// System.out.println("enque:" + r + "," + col);
}
}
/*
// 添加邻居
if(row-1 > -1) {
int c = (row-1)*n+column;
char item = grid[row-1][column];
if(item != '0'){
que.add(c);
// 避免重复添加
grid[row-1][column] = '0';
System.out.println("enque:" + (row-1) + "," + column);
}
}
if(column-1 > -1 ){
int c = row*n+column-1;
char item = grid[row][column-1];
if(item != '0'){
que.add(c);
// 避免重复添加
grid[row][column-1] = '0';
System.out.println("enque:" + row + "," + (column-1));
}
}
if(row+1 < grid.length) {
int c = (row+1)*n+column;
char item = grid[row+1][column];
if(item != '0'){
que.add(c);
// 避免重复添加
grid[row+1][column] = '0';
System.out.println("enque:" + (row+1) + "," + column);
}
}
if(column+1 < grid[row].length) {
int c = row*n+column+1;
char item = grid[row][column+1];
if(item != '0'){
que.add(c);
// 避免重复添加
grid[row][column+1] = '0';
System.out.println("enque:" + row + "," + (column+1));
}
}
*/
}
}
}
return count;
}
}
|
