代码随想录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;
}