代码随想录第51天｜岛屿数量（深搜）、岛屿数量（广搜）、岛屿的最大面积

1.岛屿数量（深搜） ---》模板题

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

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
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] &&grid[nextx][nexty] == 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] && grid[i][j] == 1) {visited[i][j] = true;result++;                 // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout << result << endl;
}

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

void dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{if(visited[x][y]||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()
{...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] && grid[i][j] == 1){result++;                 // 遇到没访问过的陆地，+1dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout << result << endl;
}

但是版本一比版本二要高效，避免了无用的递归。

2.岛屿数量（广搜）

只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
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();int curx = cur.first;int cury = cur.second;for(int i = 0; i < 4; i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if(!visited[nextx][nexty]&&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] && grid[i][j] == 1){result++;                 // 遇到没访问过的陆地，+1bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}cout << result << endl;
}

3.岛屿的最大面积

#include <iostream>
#include <vector>
using namespace std;int count = 0;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
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 || nexty < 0 || nextx >= grid.size() ||nexty >= grid[0].size()) {continue;}if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty] = true;count++;dfs(grid,visited,nextx,nexty);}}
}int main(void) {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] && grid[i][j] == 1) {visited[i][j] = true;count=1;//重置dfs(grid, visited, i, j);result = max(result, count);}}}cout<<result<<endl;return 0;
}