Leetcode刷题 | Day50_图论02_岛屿问题01_dfs两种方法+bfs一种方法

题目描述：

给定一个由 1（陆地）和 0（水）组成的矩阵，你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述：

第一行包含两个整数 N, M，表示矩阵的行数和列数。

后续 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述：

输出一个整数，表示岛屿的数量。如果不存在岛屿，则输出 0。

版本一调用dfs 的条件判断，放在，版本二的终止条件位置上。（dfs函数内部有差别）

版本一的写法：下一个节点是否能合法已经判断完了，传进dfs函数的就是合法节点。

版本二的写法：不管节点是否合法，上来就dfs，然后在终止条件的地方进行判断，不合法再return。

理论上来讲，版本一的效率更高一些，因为避免了没有意义的递归调用，在调用dfs之前，就做合法性判断。但从写法来说，可能版本二更利于理解一些。

版本一：

• dfs函数直接处理传入节点连接的四个节点
• 所以主函数中需要先将这个传入节点的visited数组值设为true，再dfs处理连接的节点
• dfs函数中，连接的节点被判断为未访问的岛屿后，再对其visited数组值设为true，再dfs处理连接的节点

两个区别：visited再哪里设置；未访问岛屿在哪里判断

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，跳过，换个方向搜索if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 未访问过，同时，是陆地（grid = 1）才继续搜索，不是陆地就直接搜索下一个方向（只能横竖连着才算一个岛）visited[nextx][nexty] = true;dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false)); // 访问数组，记录有没有访问过int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {visited[i][j] = true;result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与这个没访问陆地连接的陆地都标记上true，他们属于同一个岛，防止这些点继续被访问，被错误的计算为“未发现的新岛”，影响result计数；（！！保证连在一起的一个岛只被计数一次！！）}}}cout << result << endl;
}

版本二： 

• dfs函数直接处理传入节点
• 所以主函数中，可以直接用dfs处理该节点
• dfs函数中，先判断该节点是不是未访问的岛屿；不是就return，是就对其visited数组值设为true，再dfs处理连接的节点

两个区别：visited再哪里设置；未访问岛屿在哪里判断

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] == true || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 标记访问过for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {result++; // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout << result << endl;
}

重点：加入队列就代表走过，立即标记，而不是从队列拿出来的时候再去标记。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void bfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) { // 先加入本点，标记本点，再处理连接的四个点queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 只要加入队列，立即标记while(!que.empty()) {pair<int, int> cur = que.front();que.pop(); // 队列前面元素出队列，处理它连接的四个点for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过，搜索当前点的下一个方向if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) {que.push({nextx, nexty});visited[nextx][nexty] = true; // 只要加入队列，立即标记}}}
}
int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {result++; // 遇到没访问过的陆地，+1bfs(grid, visited, i, j); // 直接处理这个点，并将与其链接的陆地都标记上 true}}}cout << result << endl;
}

3.100岛屿的最大面积100. 岛屿的最大面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成，并且四周都是水域。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。后续 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的最大面积。如果不存在岛屿，则输出 0。

版本一dfs：dfs处理当前节点的相邻节点，即主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地 

#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 在这里判断；没有访问过的,同时是陆地的visited[nextx][nexty] = true; // 在这里处理count++; // 在这里处理；累计传入节点的连接节点的面积dfs(grid, visited, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {visited[i][j] = true; // 下面的dfs是处理相连节点的，所以这里要把当前节点visited数组值设置完count = 1;  // 因为下面的dfs处理下一个与之相连的节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}cout << result << endl;}

版本二dfs：dfs处理当前节点，即主函数遇到岛屿就计数为0，dfs处理接下来的全部陆地

#include <iostream>
#include <vector>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y] == true || grid[x][y] == 0) return; // 在这里判断；终止条件：访问过的节点 或者 遇到海水visited[x][y] = true; // 在这里处理；因为main里的dfs处理当前节点，所以main中不需要处理当前节点的visited数组值，放在这里处理count++; // 在这里处理；因为main里的dfs处理当前节点，所以main中不需要考虑当前节点的面积，放在这里处理for (int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过dfs(grid, visited, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {count = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，（现在还不需要考虑它的面积，因为交给后序dfs考虑了）进dfs之后在开始从1计数dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}cout << result << endl;
}

版本三bfs写法：处理当前节点，所以count++放在bfs函数里面的前面

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int count;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点count++;while(!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0 ;i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地visited[nextx][nexty] = true;count++;que.push({nextx, nexty});}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}vector<vector<bool>> visited(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (visited[i][j] == false && grid[i][j] == 1) {count = 0;bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}cout << result << endl;
}

4.101孤岛的总面积101. 孤岛的总面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

版本一dfs：dfs处理当前节点的连接节点 

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(vector<vector<int>>& grid, int x, int y) {for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 超过边界，不符合条件，不继续遍历if (grid[nextx][nexty] == 1) {grid[nextx][nexty] = 0;dfs (grid, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) {grid[i][0] = 0;dfs(grid, i, 0);}if (grid[i][m - 1] == 1) {grid[i][m - 1] = 0;dfs(grid, i, m - 1);}}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) {grid[0][j] = 0;dfs(grid, 0, j);}if (grid[n - 1][j] == 1) {grid[n - 1][j] = 0;dfs(grid, n - 1, j);}}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}

版本二dfs：dfs直接处理当前节点

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void dfs(vector<vector<int>>& grid, int x, int y) {if (grid[x][y] == 0) return;grid[x][y] = 0;for (int i = 0; i < 4; i++) { // 向四个方向遍历int nextx = x + dir[i][0];int nexty = y + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 超过边界，不符合条件，不继续遍历dfs (grid, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) dfs(grid, i, 0);if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}

bfs：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 四个方向
void bfs(vector<vector<int>>& grid, int x, int y) {queue<pair<int, int>> que;que.push({x, y});grid[x][y] = 0; // 只要加入队列，立刻标记while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (grid[nextx][nexty] == 1) {que.push({nextx, nexty});grid[nextx][nexty] = 0; // 只要加入队列立刻标记}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (grid[i][0] == 1) bfs(grid, i, 0);if (grid[i][m - 1] == 1) bfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (grid[0][j] == 1) bfs(grid, 0, j);if (grid[n - 1][j] == 1) bfs(grid, n - 1, j);}int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) count++;}}cout << count << endl;
}