泛洪算法（Flood Fill）

#include <iostream>
using namespace std;

int n = 5, m = 5;
char g[5][5] = {
    {'1', '1', '0', '0', '0'},
    {'1', '0', '0', '1', '1'},
    {'0', '0', '0', '1', '0'},
    {'1', '1', '0', '0', '1'},
    {'1', '1', '0', '0', '1'}
};

// 四方向偏移：必须一一对应
int dx[4] = {-1,  1, 0,  0};   // 上 下 左  右  (行)
int dy[4] = { 0,  0, -1, 1};   // 上 下 左  右  (列)

void dfs(int x, int y) {
    g[x][y] = '0';                        // 标记已访问，避免重复走
    for (int i = 0; i < 4; i++) {         // 枚举 4 个方向
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 越界判断
        if (g[nx][ny] == '1') dfs(nx, ny);                     // 继续泛洪
    }
}

int main() {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') {         // 发现新连通块
                cnt++;
                dfs(i, j);                // 把整块泛洪掉
            }
    cout << "连通块数量 = " << cnt << endl;   // 4
    return 0;
}

#include <iostream>
using namespace std;
int m,n,g[105][105];
bool v[105][105];
int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
void dfs(int x,int y){
    v[x][y]=true;
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=0&&nx<m&&ny>=0&&ny<n&&!v[nx][ny]&&g[nx][ny]==1)
            dfs(nx,ny);
    }
}
int main(){
    cin>>m>>n;
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>g[i][j];
    int cnt=0;
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)
        if(g[i][j]==1&&!v[i][j]){dfs(i,j);cnt++;}
    cout<<cnt<<endl;
}

#include <iostream>
using namespace std;
int n,g[105][105],area,maxA;
bool v[105][105];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void dfs(int x,int y){
    v[x][y]=true; area++;
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=0&&nx<n&&ny>=0&&ny<n&&!v[nx][ny]&&g[nx][ny]==1)
            dfs(nx,ny);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>g[i][j];
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)
        if(g[i][j]==1&&!v[i][j]){
            area=0; dfs(i,j);
            maxA=max(maxA,area);
        }
    cout<<maxA<<endl;
}

#include <iostream>
using namespace std;
int n,a[35][35];
bool vis[35][35];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void dfs(int x,int y){
    vis[x][y]=true;
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=0&&nx<=n+1&&ny>=0&&ny<=n+1&&!vis[nx][ny]&&a[nx][ny]==0)
            dfs(nx,ny);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
    dfs(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==0&&!vis[i][j])cout<<2<<' ';
            else cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}

#include <iostream>
#include <queue>
using namespace std;
int m,n,g[105][105],r,c;
bool vis[105][105];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
    cin>>m>>n>>r>>c;
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>g[i][j];
    queue<pair<int,int>> q;
    q.push({r,c}); vis[r][c]=true;
    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        cout<<'('<<x<<','<<y<<") ";
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&!vis[nx][ny]&&g[nx][ny]==g[r][c]){
                vis[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
    cout<<endl;
}

#include <iostream>
#include <queue>
using namespace std;
int n,g[105][105],dist[105][105];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
    cin>>n;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>g[i][j];
    if(g[0][0]==1||g[n-1][n-1]==1){cout<<-1; return 0;}
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)dist[i][j]=-1;
    queue<pair<int,int>> q;
    q.push({0,0}); dist[0][0]=0;
    while(!q.empty()){
        auto[x,y]=q.front(); q.pop();
        if(x==n-1&&y==n-1){cout<<dist[x][y]; return 0;}
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<n&&g[nx][ny]==0&&dist[nx][ny]==-1){
                dist[nx][ny]=dist[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    cout<<-1;  // 不可达
}

#include <iostream>
using namespace std;
int m,n;
char g[105][105];
bool v[105][105];
int dx[]={-1,-1,-1,0,0,1,1,1};
int dy[]={-1,0,1,-1,1,-1,0,1};
void dfs(int x,int y){
    v[x][y]=true;
    for(int d=0;d<8;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=0&&nx<m&&ny>=0&&ny<n&&!v[nx][ny]&&g[nx][ny]=='*')
            dfs(nx,ny);
    }
}
int main(){
    cin>>m>>n;
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>g[i][j];
    int cnt=0;
    for(int i=0;i<m;i++)for(int j=0;j<n;j++)
        if(g[i][j]=='*'&&!v[i][j]){dfs(i,j);cnt++;}
    cout<<cnt<<endl;
}

#include <iostream>
using namespace std;
int n,m,g[105][105],id_map[105][105],area,maxA,cnt;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void dfs(int x,int y,int id){
    id_map[x][y]=id; area++;
    for(int d=0;d<4;d++){
        int nx=x+dx[d],ny=y+dy[d];
        if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==1&&id_map[nx][ny]==0)
            dfs(nx,ny,id);
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>g[i][j];
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
        if(g[i][j]==1&&id_map[i][j]==0){
            cnt++; area=0;
            dfs(i,j,cnt);
            maxA=max(maxA,area);
        }
    cout<<"岛屿数: "<<cnt<<endl;
    cout<<"最大面积: "<<maxA<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)cout<<id_map[i][j]<<' ';
        cout<<endl;
    }
}

#include <iostream>
#include <queue>
using namespace std;
int n,m,g[105][105],dist[105][105];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int main(){
    cin>>n>>m;
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        cin>>g[i][j]; dist[i][j]=-1;
        if(g[i][j]==1){q.push({i,j}); dist[i][j]=0;}
    }
    while(!q.empty()){
        auto[x,y]=q.front(); q.pop();
        for(int d=0;d<4;d++){
            int nx=x+dx[d],ny=y+dy[d];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&dist[nx][ny]==-1){
                dist[nx][ny]=dist[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)cout<<dist[i][j]<<' ';
        cout<<endl;
    }
}