5 条题解

  • 0
    @ 2026-4-7 16:57:06
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    /* 是一个经典的染色法--(后悔跟y总学的时候跳了) 
      岛屿数量本题可以用DFS/BFS进行写 
      统一思路:1将数组放入1,1开始 但遍历从0,0没有越界考虑
                2 遍历数组找1 直接ans++ 然后进入DFS/BFS进行处理把这部分岛屿全变成海
    			本题用BFS写吧  
    */
    #define PII pair<int,int>
    const int N=550;
    int a[N][N];
    int dx[]={1,-1,0,0};
    int dy[]={0,0,-1,1};
    int n;
    int ans; 
    //本题的 BFS/DFS都是解决局部问题即单个岛屿 
    void bfs(int x,int y)
    { queue<PII> q;
      a[x][y]=0;//染色
      q.push({x,y});
      while(q.size())
      {
      	auto t=q.front();
      	q.pop();
       int xx=t.first;
       int yy=t.second;  	
      for(int i=0;i<4;i++)
       {
         int nx=xx+dx[i];
    	 int ny=yy+dy[i];
    	 if(a[nx][ny]==1)
    	 {
    	   a[nx][ny]=0;
    	   q.push({nx,ny});	
    	 }	
       }	
      }
      return;
    }
    signed main()
    { std::ios::sync_with_stdio(0);
      cin.tie(0),cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	 for(int j=1;j<=n;j++)
    	  cin>>a[i][j];
    	for(int i=1;i<=n;i++)
       {
    	    for(int j=1;j<=n;j++)
    	 	if(a[i][j]==1) 
    	 	{
    	 	 ans++;
    		 bfs(i,j); 	
    		}  
       }
    	cout<<ans<<"\n"; 	
    	return 0;
    }

    信息

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