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; }
-
-12018-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
-
-32021-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
- 上传者