5 条题解
-
0
#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
- 上传者