2 条题解
-
-2武子涵@石湖中学 (武子涵) LV 10 @ 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
-
-22018-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
- 1
信息
- 难度
- 8
- 分类
- (无)
- 标签
- (无)
- 递交数
- 82
- 已通过
- 11
- 通过率
- 13%
- 被复制
- 3
- 上传者