题目地址：力扣
思路：我们从题目中可以得知，孤立的岛屿旁边全是海，假设岛屿范围内每一个‘1’是岛屿的一部分，那么我们从岛屿的任意一部分登岛，走遍岛屿的每一块土地，就能确定岛屿的大小和范围。为了找遍所有的岛屿，我们还需要把走过的土地都标记为0，防止从同一岛屿的另一部分登岛。因此，我们只。需要通过'1'的部分登岛，走遍岛屿；记录岛屿的数量加1，再继续找还没有'1'的部分，走遍下一个岛屿。以此类推，直到遍历完所有的地方，就能确定岛屿的数量。比如下面的例子，不同颜色的'1'表示不同岛屿的一部分。下面有三种颜色，因此岛屿总数为3
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","1","0","1"]
解法1：深度优先搜索
既然是要走遍岛屿，那么首先就可以想到的是DFS。思路就是上面的思路，实现代码如下：
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j)
{
// 当前部分走过了，因此把当前部分置为0
grid[i][j] = '0';
// 依次看看上下左右是不是还有同属岛屿的其他部分
// 若有，则依次遍历并置为0
if (i > 0 && grid[i-1][j] == '1')
dfs(grid, i-1, j);
if (i < grid.size()-1 && grid[i+1][j] == '1')
dfs(grid, i+1, j);
if (j > 0 && grid[i][j-1] == '1')
dfs(grid, i, j-1);
if (j < grid[0].size()-1 && grid[i][j+1] == '1')
dfs(grid, i, j+1);
}
int numIslands(vector<vector<char>>& grid) {
// 分别记录行、列以及岛屿总数
int row = grid.size();
int col = grid[0].size();
int cnt = 0;
// 从第一行第一列开始，寻找有没有是'1'的位置，若有，则登岛遍历，岛屿数加1
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
if (grid[i][j] == '1')
{
dfs(grid, i, j);
++cnt;
}
}
}
// 返回岛屿的总数
return cnt;
}
};
解法2：广度优先搜索
既然要走遍岛屿的每一部分，那么广度优先也可以实现相同的目的，代码如下：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int row = grid.size();
int col = grid[0].size();
int cnt = 0;
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
// 只要找到了一个为'1'的，那么登岛
if (grid[i][j] == '1')
{
// 当前找到的新岛屿，数量加1
++cnt;
// 广度优先，那么需要借助队列来实现
queue<pair<int, int>> bfs_q;
// 把当前走过的地方置0
grid[i][j] = 0;
bfs_q.push({i, j});
// 只要队不空就循环
while (!bfs_q.empty())
{
// 取出队头元素，出队
auto cur = bfs_q.front();
bfs_q.pop();
// 判断队头元素的上下左右是否有岛屿的其他部分，有的话则入队并置0
if (cur.first > 0 && grid[cur.first-1][cur.second] == '1')
{
bfs_q.push({cur.first-1, cur.second});
grid[cur.first-1][cur.second] = 0;
}
if (cur.first < row-1 && grid[cur.first+1][cur.second] == '1')
{
bfs_q.push({cur.first+1, cur.second});
grid[cur.first+1][cur.second] = 0;
}
if (cur.second > 0 && grid[cur.first][cur.second-1] == '1')
{
bfs_q.push({cur.first, cur.second-1});
grid[cur.first][cur.second-1] = 0;
}
if (cur.second < col-1 && grid[cur.first][cur.second+1] == '1')
{
bfs_q.push({cur.first, cur.second+1});
grid[cur.first][cur.second+1] = 0;
}
}
}
}
}
return cnt;
}
};
注意：对于这道题来说，广度优先遍历值得注意的地方在于，要先把当前出队的元素上下左右置0（若有岛屿部分），然后再把那些置过0的元素入队。而不能先把上下左右的元素入队，等出队的时候再置0。因为后面这种操作可能会造成相同元素的重复入队，从而导致超出限制时间。
解法3：并查集
思路：我们在遍历的时候会发现有些位置是'1'（陆地），而有些位置是'0'（海洋），但是我们不确定岛屿的面积有多大，即陆地周围是否还会出现陆地。如果出现陆地，那么这两块陆地就同属于一篇岛屿。这种情况显然可以使用并查集来将同属一块岛屿的陆地归类在一起，同属一块岛屿的陆地其父节点应该是相同的。
我们可以用一个数组来表示所有区域的父节点，初始化另所有区域的父节点都等于自身，同时计算陆地的数量。第二次遍历的时候，首先判断当前区域是否是陆地，接着判断当前陆地下方和右方是否还有陆地，若有的话，则将这两块陆地合并，将陆地数量减一，继续遍历下一个节点。若当前区域不是陆地则跳过。这样遍历完所有区域，陆地的数量就应该等于岛屿的数量。因此返回陆地数量即可。
class Solution {
public:
int find(int idx)
{
// 若当前节点的父节点就是自己，那么只需要返回自己
if (parent[idx] == idx)
return idx;
// 路径压缩，只要idx节点的父节点不是整个集合的头节点，那么就把路径上每个节点都向集合的头结点
parent[idx] = find(parent[idx]);
// 返回idx的父节点（也是整个集合的头节点）
return parent[idx];
}
void union_n (int idx_1, int idx_2)
{
int par_1 = find(idx_1);
int par_2 = find(idx_2);
// 若idx_1和idx_2的父节点是同一个，那就不做任何操作
if (par_1 == par_2)
return;
// 原本par_1和par_2分别是idx_1和idx_2的父节点，因此都指向自己
// 这个赋值将par_1的父节点指向了par_2，完成了合并操作
parent[par_1] = par_2;
// 每当一块陆地拼进了岛屿，那么陆地数量自减
--land_num;
}
int numIslands(vector<vector<char>>& grid) {
// 输入的行与列
int row = grid.size();
int col = grid[0].size();
// 初始化陆地数量以及数组
land_num = 0;
parent = vector<int> (row*col, -1);
// 构建并查集
for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j)
{
if (grid[i][j] == '1')
++land_num;
// 初始化父亲节点都为自己
parent[i*col + j] = i*col + j;
}
// 进行并查的过程
for (int i = 0; i < row; ++i)
for (int j = 0; j <col; ++j)
{
if (grid[i][j] == '1')
{
// 从左往右逐行遍历，若下方或者右方的节点也是陆地，那么就拼在一起
if (i + 1 < row && grid[i+1][j] == '1')
union_n(i*col+j, (i+1)*col+j);
if (j + 1 < col && grid[i][j+1] == '1')
union_n(i*col+j, i*col+j+1);
}
}
// 返回剩下的陆地数量（岛屿数量）
return land_num;
}
private:
// 记录父节点以及陆地的数量
vector<int> parent;
int land_num;
};
Accepted
- 49/49 cases passed (28 ms)
- Your runtime beats 88.07 % of cpp submissions
- Your memory usage beats 77.52 % of cpp submissions (11.9 MB)
