3 条题解
- 
  0Infinity_ LV 8 @ 2024-08-22 17:11:12 #include<bits/stdc++.h> #define N 1010 using namespace std; char b[N][N]; bool vis[N][N]; int p[8][3] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -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 < 8; i++){ int nx = q[head].x + p[i][0], ny = q[head].y + p[i][1]; if(nx >= 0 && nx <= m+1 && ny >= 0 && ny <= n+1 && b[nx][ny] == '0' && !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)); memset(b, 0, sizeof(b)); 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] == '0' && !vis[i][j]){ cnt++; bfs(i, j); } } } cout << (cnt-1)/2; return 0; }
- 
  -1@ 2018-12-11 12:00:29/* */ #define method_1 #ifdef method_1 /* 100分算法 种子填充 找到有几个含0的联通块 记录其个数为cnt 则答案就是cnt-1后除以二 */ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> using namespace std; typedef long long ll; const int maxn=100+5; const ll INF=0x3f3f3f3f3f3f3f3fll; const int dx[]= {0,-1,0,1}; const int dy[]= {1,0,-1,0}; int n,m; char a[maxn][maxn]; int vis[maxn][maxn]; bool check(int x,int y) { if(x<0||x>(n+1)||y<0||y>(m+1)) return false; return true; } void dfs(int x,int y,int c) { if(check(x,y)==false) return; if(vis[x][y]||(a[x][y]!='0')) return; vis[x][y]=c; for(int i=0; i<=3; i++) { int newx=x+dx[i]; int newy=y+dy[i]; // if(check(newx,newy)&&(vis[newx][newy]==0)&&a[newx][newy]=='0'){ // vis[newx][newy]=c; dfs(newx,newy,c); // } } } int main() { ios::sync_with_stdio(false); freopen("偷拍硕哥3.in","r",stdin); for(int i=0; i<=n+1; i++) { for(int j=0; j<=m+1; j++) { a[i][j]='0'; vis[i][j]=0; } } 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++){ cout<<a[i][j]; } cout<<endl; } */ int cnt=0; for(int i=0; i<=n+1; i++) { for(int j=0; j<=m+1; j++) { if((a[i][j]=='0')&&(vis[i][j]==0)) { dfs(i,j,++cnt); } } } /* for(int i=0; i<=n+1; i++) { for(int j=0; j<=m+1; j++) { cout<<vis[i][j]; } cout<<endl; } */ cout<<(cnt-1)/2; return 0; } #endif #ifdef method_2 /* */ #endif #ifdef method_3 /* */ #endif
- 
  -3@ 2021-03-13 13:50:27/* / 
 #define method_1
 #ifdef method_1
 /
 100分算法
 种子填充 找到有几个含0的联通块 记录其个数为cnt
 则答案就是cnt-1后除以二
 /
 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #include<cmath>
 #include<set>
 #include<map>
 #include<queue>
 #include<stack>
 #include<vector>
 #include<cstring>
 #include<cstdlib>
 using namespace std;
 typedef long long ll;
 const int maxn=100+5;
 const ll INF=0x3f3f3f3f3f3f3f3fll;
 const int dx[]= {0,-1,0,1};
 const int dy[]= {1,0,-1,0};
 int n,m;
 char a[maxn][maxn];
 int vis[maxn][maxn];
 bool check(int x,int y) {
 if(x<0||x>(n+1)||y<0||y>(m+1)) return false;
 return true;
 }
 void dfs(int x,int y,int c) {
 if(check(x,y)==false) return;
 if(vis[x][y]||(a[x][y]!='0')) return;
 vis[x][y]=c;
 for(int i=0; i<=3; i++) {
 int newx=x+dx[i];
 int newy=y+dy[i];
 // if(check(newx,newy)&&(vis[newx][newy]==0)&&a[newx][newy]=='0'){
 // vis[newx][newy]=c;
 dfs(newx,newy,c);
 // }
 }
 }
 int main() {
 ios::sync_with_stdio(false);
 freopen("偷拍硕哥3.in","r",stdin);
 for(int i=0; i<=n+1; i++) {
 for(int j=0; j<=m+1; j++) {
 a[i][j]='0';
 vis[i][j]=0;
 }
 }
 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++){
 cout<<a[i][j];
 }
 cout<<endl;
 }
 /
 int cnt=0;
 for(int i=0; i<=n+1; i++) {
 for(int j=0; j<=m+1; j++) {
 if((a[i][j]=='0')&&(vis[i][j]==0)) {
 dfs(i,j,++cnt);
 }
 }
 }
 /
 for(int i=0; i<=n+1; i++) {
 for(int j=0; j<=m+1; j++) {
 cout<<vis[i][j];
 }
 cout<<endl;
 }
 /
 cout<<(cnt-1)/2;
 return 0;
 }
 #endif
 #ifdef method_2
 /*/ #endif 
 #ifdef method_3
 /**/ #endif 
- 1
信息
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 84
- 已通过
- 12
- 通过率
- 14%
- 被复制
- 3
- 上传者