3 条题解

  • 0
    @ 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

    /*

    /
    #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
上传者