代码随想录day51图论2

99. 岛屿数量

题目链接
文章讲解

dfs

#include<bits/stdc++.h>
using namespace std;vector<int> path;  // 存储路径（此变量在当前代码中未使用，但可能是为了其他操作预留的）
int ans;  // 记录连通区域的数量
// 方向数组，表示四个可能的方向：右、下、左、上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// 深度优先搜索（DFS）函数，用于遍历二维网格
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y)
{// 如果当前位置是水域（值为0）或已经访问过，返回if(grid[x][y] == 0 || visit[x][y]) return;// 标记当前位置已访问visit[x][y] = true;// 遍历四个方向for(int i = 0; i < 4; i++){// 计算下一个位置的坐标int nextx = x + direct[i][0];int nexty = y + direct[i][1];// 如果下一个位置超出边界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 递归调用 DFS 函数dfs(grid, visit, nextx, nexty);}
}int main(){int n, m;  // n表示行数，m表示列数cin >> n >> m;  // 输入网格的大小vector<vector<int>> grid(n, vector<int>(m, 0));  // 初始化网格，默认值为0（表示水域）vector<vector<bool>> visit(n, vector<bool>(m, false));  // 初始化访问标记，默认值为false（表示未访问）// 输入网格数据，1表示陆地，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++){for(int j = 0; j < m; j++){// 如果当前是陆地且未访问过，启动一个新的 DFS 遍历，发现一个新的连通区域if(grid[i][j] == 1 && !visit[i][j]){ans++;  // 新发现一个连通区域dfs(grid, visit, i, j);  // 深度优先搜索遍历该区域}}}// 输出连通区域的数量cout << ans;
}

bfs

文章讲解

#include<bits/stdc++.h>
using namespace std;int ans;
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 定义四个方向：右，下，左，上int main(){int n, m;cin >> n >> m;// 初始化网格和访问数组vector<vector<int>> grid(n, vector<int>(m, 0));vector<vector<bool>> visit(n, vector<bool>(m, false));// 输入网格数据for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];}}// 遍历网格，使用 BFS 搜索每一个未访问的陆地区域for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!visit[i][j] && grid[i][j] == 1)  // 如果是陆地且未访问{ans++;  // 找到一个新的连通区域queue<pair<int, int>> q;q.push({i, j});visit[i][j] = true;  // 标记为已访问// 开始 BFS 搜索while(!q.empty()){pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for(int i = 0; i < 4; i++){int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果越界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果是陆地且未访问过，加入队列if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});visit[nextx][nexty] = true;}}}}}}// 输出连通区域的数量cout << ans;
}

#include<bits/stdc++.h>
using namespace std;vector<int> path;
int ans;
int direct[4][2]={0,1,1,0,-1,0,0,-1};
void bfs(vector<vector<int>>& grid,vector<vector<bool>>& visit,int x,int y)
{queue<pair<int,int>> q;q.push({x,y});visit[x][y]=true;while(!q.empty()){pair<int,int> cur=q.front();q.pop();int curx=cur.first;int cury=cur.second;for(int i=0;i<4;i++){int nextx=curx+direct[i][0];int nexty=cury+direct[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()) continue;if(grid[nextx][nexty]==1&&!visit[nextx][nexty]){q.push({nextx,nexty});visit[nextx][nexty]=true;}}}}
int main(){int n,m;cin>>n>>m;vector<vector<int>> grid(n,vector<int>(m,0));vector<vector<bool>> visit(n,vector<bool>(m,false));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++){for(int j=0;j<m;j++){if(!visit[i][j]&&grid[i][j]==1) {ans++;bfs(grid,visit,i,j);}}}cout<<ans;
}

100. 岛屿的最大面积

题目链接
文章讲解
bfs

#include<bits/stdc++.h>
using namespace std;vector<int> path;  // 存储路径（当前代码中未使用，但可能为将来扩展保留的）
int ans;           // 记录连通区域的数量
int res;           // 记录最大的连通区域的大小
// 四个方向：右，下，左，上
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};// 广度优先搜索（BFS）函数
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y, int& sum)
{// 使用队列来进行广度优先搜索queue<pair<int, int>> q;q.push({x, y});visit[x][y] = true;  // 标记当前点为已访问while(!q.empty()){// 取出队列中的当前元素pair<int, int> cur = q.front();q.pop();int curx = cur.first;int cury = cur.second;// 遍历四个方向for(int i = 0; i < 4; i++){// 计算下一个位置的坐标int nextx = curx + direct[i][0];int nexty = cury + direct[i][1];// 如果下一个位置越界，跳过if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;// 如果下一个位置是陆地且未访问过if(grid[nextx][nexty] == 1 && !visit[nextx][nexty]){q.push({nextx, nexty});  // 将新的位置加入队列visit[nextx][nexty] = true;  // 标记该位置为已访问sum++;  // 当前连通区域的大小加一}}}
}int main(){int n, m;cin >> n >> m;  // 输入网格的行数和列数// 初始化网格和访问标记数组vector<vector<int>> grid(n, vector<int>(m, 0));  // 网格，0表示水域，1表示陆地vector<vector<bool>> visit(n, vector<bool>(m, false));  // 访问标记数组，初始为未访问// 输入网格的数据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++){for(int j = 0; j < m; j++){// 如果该位置是陆地且未访问过，说明发现了一个新的连通区域if(!visit[i][j] && grid[i][j] == 1){ans++;  // 连通区域数量加一int sum = 1;  // 当前连通区域的大小（包括当前位置）// 使用 BFS 扩展该连通区域bfs(grid, visit, i, j, sum);// 更新最大的连通区域大小res = max(sum, res);}}}// 输出最大的连通区域大小cout << res;
}