3 条题解
-
1Infinity_ LV 8 @ 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; }
-
12023-07-27 09:05:22@
//既然有深搜代码了,那就再附个宽搜的 #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; }
-
02023-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%
- 上传者