5 条题解
-
1huhe (huangjiasheng) LV 9 @ 2022-1-25 15:19:50
/********************************* 备注: *********************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <queue> #include <math.h> #include <vector> #include <algorithm> #include <iomanip> #include <stack> using namespace std; #define LL long long const int N =1e5+10; const int INF =0x3f3f3f3f; int mp[100][100],a[100][100],n,m; int dx[]{0,-1,0,1}; int dy[]{-1,0,1,0}; struct node{ int x,y; }; int bfs(int x,int y){ queue<node> p; p.push((node){x,y}); a[x][y]=1; int sum=1; while(!p.empty()){ node t=p.front(); p.pop(); for(int i=0;i<4;i++){ x=t.x+dx[i]; y=t.y+dy[i]; int s=mp[t.x][t.y]&(1<<i); if(s==0&&!a[x][y]){ a[x][y]=++sum; p.push((node){x,y}); } } } return sum; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>mp[i][j]; } } int num=0,maxx=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]==0){ num++; maxx=max(maxx,bfs(i,j)); } } } cout<<num<<endl; cout<<maxx<<endl; return 0; }
-
02024-2-3 10:13:01@
#include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<cstring> #include<bits/stdc++.h> using namespace std; int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; int ans=0; int n,m,x,y,b,maxx; int a[100][100],v[100][100]; struct node{ int x,y; }; queue<node>q; void bfs(int x,int y){ q.push((node){x,y}); int cnt=1; v[x][y]=1; while(!q.empty()){ node top=q.front(); q.pop(); for(int i=0;i<=3;i++){ int xx=top.x+dx[i]; int yy=top.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]==0&&(a[top.x][top.y]&(1<<i))==0){ cnt++; v[xx][yy]=1; q.push((node){xx,yy}); } } } maxx=max(maxx,cnt); } 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(v[i][j]==0){ ans++; bfs(i,j); } } } cout<<ans<<endl<<maxx; }
-
02024-2-1 9:45:48@
#include<iostream> #include<bits/stdc++.h> using namespace std; const int N=1145; int a[N][N]; bool v[N][N]; int m,n,maxx,ans; int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; struct node{ int x,y; }; queue<node>q; void bfs(int x,int y){ q.push((node){x,y}); int cnt=1; v[x][y]=1; while(!q.empty()){ node top=q.front(); q.pop(); for(int i=0;i<=3;i++){ int xx=top.x+dx[i]; int yy=top.y+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]==0&&(a[top.x][top.y]&(1<<i))==0){ cnt++; v[xx][yy]=1; q.push((node){xx,yy}); } } } maxx=max(maxx,cnt); } 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(v[i][j]==0) { ans++; bfs(i,j);
}
}
cout<<ans<<endl<<maxx; return 0; }
-
02024-1-31 17:02:28@
#include <stdio.h> #include <queue> #include <stack> #include <algorithm> #include <iostream> #include <math.h> #include <string.h> #include <vector> #define LL long long const int INF = 0x3f3f3f3f; const int N = 50+10; using namespace std; int n , m , a[N][N] , ans , maxx; bool v[N][N]; int dx[] = {0, -1 , 0 , 1};//西北东南 int dy[] = {-1, 0 , 1 , 0}; struct node { int x , y; }; queue<node> q; void bfs(int x , int y) { q.push((node){x , y}); int cnt = 1; v[x][y] = 1; while(!q.empty()) { node top = q.front(); q.pop(); for(int i = 0 ; i <= 3; i++) { int xx = top.x + dx[i]; int yy = top.y + dy[i]; //(a[top.x][top.y] & (1 << i)) == 0 判断是否有墙 if( xx >= 1 && xx <= n && yy >= 1 && yy <= m && v[xx][yy] == 0 && (a[top.x][top.y] & (1 << i)) == 0 ) { cnt++; v[xx][yy] = 1; q.push((node){xx , yy}); } } } maxx = max(maxx , cnt); } 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(v[i][j] == 0)//当前点没有访问过 { ans++; bfs(i , j); } } cout << ans << endl << maxx; return 0; }
-
02022-1-17 21:50:45@
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> #include <math.h> #include <vector> #include <algorithm> #include <iomanip> #include <stack> using namespace std; #define LL long long const int N =1e5+10; const int INF =0x3f3f3f3f; int mp[100][100],a[100][100],n,m; int dx[]{0,-1,0,1}; int dy[]{-1,0,1,0}; struct node{ int x,y; }; int bfs(int x,int y){ queue<node> p; p.push((node){x,y}); a[x][y]=1; int sum=1; while(!p.empty()){ node t=p.front(); p.pop(); for(int i=0;i<4;i++){ x=t.x+dx[i]; y=t.y+dy[i]; int s=mp[t.x][t.y]&(1<<i); if(s==0&&!a[x][y]){ a[x][y]=++sum; p.push((node){x,y}); } } } return sum; } int main(){ cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>mp[i][j]; } } int num=0,maxx=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]==0){ num++; maxx=max(maxx,bfs(i,j)); } } } cout<<num<<endl; cout<<maxx<<endl; return 0; }
- 1
信息
- ID
- 1344
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 120
- 已通过
- 53
- 上传者