1 solutions
-
1
#include<bits/stdc++.h> using namespace std; const int N=10010; char g[N][N]; int dx[]={-1,0,0,1}; int dy[]={0,-1,1,0}; bool st[N][N]; int n,m; struct Node{ int x,y; }; void bfs(int x,int y) { queue<Node> q; q.push({x,y}); st[x][y]=1; while(q.size()) { Node t=q.front(); q.pop(); int x=t.x,y=t.y; for(int i=0;i<4;i++) { int a=x+dx[i],b=y+dy[i]; if(a<1 || a>n || b<1 || b>m) { continue; } if(g[a][b]=='0') { continue; } if(st[a][b]) { continue; } st[a][b]=1; q.push({a,b}); } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>g[i][j]; } } int res=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(g[i][j]!='0' && !st[i][j]) { //cout<<i<<" "<<j<<endl; bfs(i,j); res++; } } } cout<<res; return 0; }
- 1
Information
- ID
- 1005
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- (None)
- # Submissions
- 53
- Accepted
- 11
- Uploaded By