问题描述
给定一个二维数组，其中 0 表示水，1 表示陆地，要求找出岛屿（1相连但是被 0 包围）的数量。题目链接：**点我**
样例输入输出
输入：
[
[‘1’,’1’,’1’,’1’,’0’],
[‘1’,’1’,’0’,’1’,’0’],
[‘1’,’1’,’0’,’0’,’0’],
[‘0’,’0’,’0’,’0’,’0’]
]
输出：1
输入：
[
[‘1’,’1’,’0’,’0’,’0’],
[‘1’,’1’,’0’,’0’,’0’],
[‘0’,’0’,’1’,’0’,’0’],
[‘0’,’0’,’0’,’1’,’1’]
]
输出：3
问题解法
循环遍历每个元素，如果遇到 1 ，则使用广搜算法，将当前与这个 1 相连的所有 1 都变成 2，同时记录更新当前岛屿数量加一，遍历结束后，最终累计的结果就是岛屿的数量。代码如下
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
| class Solution
{
public int numIslands(char[][] grid)
{
int count = 0;
for (int i = 0; i < grid.length; i++)
{
for (int j = 0; j < grid[0].length; j++)
{
if (grid[i][j] == '1')
{
count++;
travelIsland(grid, i, j);
}
}
}
return count;
}
private void travelIsland(char[][] grid, int i, int j)
{
grid[i][j] = '2';
Queue<int[]> queue = new LinkedList<>();
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
int[] begin = {i, j};
queue.offer(begin);
while (!queue.isEmpty())
{
int[] current = queue.poll();
for (int k = 0; k < dx.length; k++)
{
int[] next = {current[0] + dx[k], current[1] + dy[k]};
if (next[0] >=0 && next[0] < grid.length && next[1] >= 0 && next[1] < grid[0].length && grid[next[0]][next[1]] == '1')
{
grid[next[0]][next[1]] = '2';
queue.offer(next);
}
}
}
}
}
|