8 条题解

  • 1
    @ 2026-5-28 15:01:38
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 510;
    int g[N][N];
    bool vis[N][N];
    int n;
    const int dx[] = {-1,0,1,0};
    const int dy[] = {0,1,0,-1};
    
    void bfs(int x,int y){
    	queue<pair<int,int>> q;
    	q.push({x,y});
    	vis[x][y] = true;
    	
    	while(!q.empty()){
    		auto it = q.front();
    		q.pop();
    		int xx = it.first,yy = it.second;
    		
    		for(int i=0;i<4;i++){
    			int nx = xx + dx[i],ny = yy + dy[i];
    			if(nx>=1&&nx<=n&&ny>=1&&ny<=n){
    				if(!vis[nx][ny]&&g[nx][ny]==1){
    					vis[nx][ny] = true;
    					q.push({nx,ny});
    				}
    			}
    		}
    	}
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>g[i][j];
    		}
    	}
        int res=0;
        for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			if(!vis[i][j]&&g[i][j]==1){
    				bfs(i,j);
    				res++;
    			}
    		}
    	}
        cout<<res;
        return 0;
    }
    

    信息

    ID
    33
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    443
    已通过
    185
    上传者