2 条题解

  • -2

    /*

    /
    #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

  • -2
    @ 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
    
    
  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
82
已通过
11
通过率
13%
被复制
3
上传者