BM57. [岛屿数量]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM57. 岛屿数量
题目的主要信息：
- 给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛
- 只考虑上下左右为相邻
- 判断岛屿的个数
方法一：dfs
具体做法：
可以从上到下从左到右依次遍历矩阵，每次遇到一个1则岛屿数记为1，然后将与这个1及与其相邻的所有1全部置为0，相当于这个岛屿已经被统计了，避免重复统计。
将邻近的1全部置为0的方法，我们可以用dfs。从每次遍历到的第一个1为起点，分别向四个方向进行深度优先搜索，注意不能越界且值为1才能搜索过去，到达每个节点，将其值置为0即可。
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j) { //深度优先遍历与i，j相邻的所有1
int n = grid.size();
int m = grid[0].size();
grid[i][j] = '0'; // 置为0
//后续四个方向遍历
if(i - 1 >= 0 && grid[i - 1][j] == '1')
dfs(grid, i - 1, j);
if(i + 1 < n && grid[i + 1][j] == '1')
dfs(grid, i + 1,j);
if(j - 1 >= 0 && grid[i][j - 1] == '1')
dfs(grid, i, j - 1);
if(j + 1 < m && grid[i][j + 1] == '1')
dfs(grid, i, j + 1);
}
int solve(vector<vector<char> >& grid) {
int n = grid.size();
if (n == 0) //空矩阵的情况
return 0;
int m = grid[0].size();
int count = 0; //记录岛屿数
for(int i = 0; i < n; i++){ // 遍历矩阵
for(int j = 0; j < m; j++){
if(grid[i][j] == '1'){ //遍历到1的情况
count++; //计数
dfs(grid, i, j); //将与这个1相邻的所有1置为0
}
}
}
return count;
}
};
复杂度分析：
- 时间复杂度：
，其中
、
为矩阵的长和宽，需要遍历整个矩阵，每次dfs搜索需要经过每个值为1的元素，但是最坏情况下也只是将整个矩阵变成0，因此相当于最坏遍历矩阵2次
- 空间复杂度：
方法二：bfs
具体做法：
统计岛屿的方法可以不变，但是将相邻的1全部置为0的方法还可以使用bfs。
利用队列辅助，每次队列进入第一个进入的1，然后遍历队列，依次探讨队首的四个方向，是否符合，如果符合则置为0，且位置坐标加入队列，继续遍历，直到队列为空。
class Solution {
public:
int solve(vector<vector<char> >& grid) {
int n = grid.size();
if(n == 0) //空矩阵的情况
return 0;
int m = grid[0].size();
int count = 0; //记录岛屿数
for(int i = 0; i < n; i++){ // 遍历矩阵
for(int j = 0; j < m; j++){
if(grid[i][j] == '1'){ //遇到1要将这个1及与其相邻的1都置为0
count++; //岛屿数增加
grid[i][j] = '0';
queue<pair<int, int>> q; //记录后续bfs的坐标
q.push({i, j});
while(!q.empty()){ //bfs
auto temp = q.front();
q.pop();
int row = temp.first;
int col = temp.second;
//四个方向依次检查：不越界且为1
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
q.push({row - 1, col});
grid[row - 1][col] = '0';
}
if(row + 1 < n && grid[row + 1][col] == '1'){
q.push({row + 1, col});
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
q.push({row, col - 1});
grid[row][col - 1] = '0';
}
if(col + 1 < m && grid[row][col + 1] == '1'){
q.push({row, col + 1});
grid[row][col + 1] = '0';
}
}
}
}
}
return count;
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
，bfs最坏情况队列大小为长和宽的较小值
