3 条题解

  • 1
    @ 2024-08-22 15:41:29
    #include<bits/stdc++.h>
    #define N 110
    using namespace std;
    bool b[N][N], vis[N][N];
    int p[5][3] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}, m, n;
    struct node{
        int x, y;
    }q[N];
    void bfs(int x, int y){
        int head = 1, tail = 1;
        q[tail].x = x; q[tail].y = y;
        tail++;
        while(head < tail){
            vis[q[head].x][q[head].y] = 1;
            for(int i = 0; i < 4; i++){
                int nx = q[head].x + p[i][0], ny = q[head].y + p[i][1];
                if(nx >= 1 && nx <= m  &&  ny >= 1 && ny <= n  &&  b[nx][ny]  &&  !vis[nx][ny]){
                    q[tail].x = nx; q[tail].y = ny;  //入队
                    tail++;
                    vis[nx][ny] = 1;
                }
            }
            head++;  //队头出队 
        }
    }
    int main(){
        ios::sync_with_stdio(false);
        int cnt = 0;
        cin >> m >> n;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++)cin >> b[i][j];
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(b[i][j] && !vis[i][j]){
                    cnt++;
                    bfs(i, j);
                }
            }
        }
        cout << cnt;
        return 0;
    }
    
  • 1
    //既然有深搜代码了,那就再附个宽搜的 
    #include<bits/stdc++.h>
    using namespace std;
    short dir[4][2]={0,1,1,0,0,-1,-1,0},q[1005][2],n,m,ans,ch[105][105];
    bool vis[105][105];
    void bfs(int i,int j)
    {
        vis[i][j]=1;
        int f=1,r=1;q[1][0]=i,q[1][1]=j;
        while(f<=r)
        {
            int x=q[f][0],y=q[f][1];
            for(int c=0;c<4;c++)
            {
                int nx=dir[c][0]+x,ny=dir[c][1]+y;
                if(ch[nx][ny]&&!vis[nx][ny]&&nx>=1&&nx<=n&&ny>=1&&ny<=m)
                {
                    r++;
                    q[r][0]=nx,q[r][1]=ny;
                    vis[nx][ny]=1;
                }
            }
            f++;
        }
        ans++;
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>ch[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(ch[i][j]&&!vis[i][j])
                    bfs(i,j);
        cout<<ans<<endl;
        return 0;
    }
    
    
  • 0
    @ 2023-06-27 21:47:43
    //轻松accepted
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,a[105][105],ans;
    int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    bool vis[105][105];
    void dfs(int x,int y)
    {
        vis[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(a[nx][ny]==1&&!vis[nx][ny])
            {
                vis[nx][ny]=true;
                dfs(nx,ny);
            }
        }
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(!vis[i][j]&&a[i][j]==1)
                {
                    ans++;
                    dfs(i,j);
                }
            }
        cout<<ans<<endl;
        return 0;
    }
    
  • 1

信息

ID
1236
难度
4
分类
(无)
标签
递交数
25
已通过
15
通过率
60%
上传者