dfs 36分求助

Aakkosetsumussa @ 2023-01-11 21:52:25

#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
typedef long double onr;
#define fr(y) for(inr i=1;i<=y;i++)
int n,a[1007][1007],b[1007][1007],ca=0,cb=0,via[1007][1007],vib[1007][1007];
char ch;
int dx[]= {0,1,-1,0, 0};
int dy[]= {0,0, 0,1,-1};
inline void dfsa(int x,int y) {
    if(via[x][y]==0) ca++,via[x][y]=1;
    fr(4) {
        int tx=x+dx[i],ty=y+dy[i];
        if(a[tx][ty]==1&&1<tx&&tx<n&&1<ty&&ty<n&&!via[tx][ty]) {
            via[tx][ty]=1;
            dfsa(tx,ty);
        }
    }
}
inline void dfsb(int x,int y) {
    if(vib[x][y]==0) cb++,vib[x][y]=1;
    fr(4) {
        int tx=x+dx[i],ty=y+dy[i];
        if(b[tx][ty]==1&&1<tx&&tx<n&&1<ty&&ty<n&&!vib[tx][ty]) {
            vib[tx][ty]=1;
            dfsb(tx,ty);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    fr(n)
    for(int j=1; j<=n; j++) {
        cin>>ch;
        if(ch=='#') a[i][j]=1;
    }
    fr(n)
    for(int j=1; j<=n; j++)
        if(a[i][j]&&via[i][j]==0)
            dfsa(i,j);
    /*
    fr(n) {
        for(int j=1; j<=n; j++) cout<<via[i][j]<<" ";
        cout<<endl;
    }//*/
    fr(n)
    for(int j=1; j<=n; j++)
        if(a[i][j]==1)
            if(a[i-1][j]==1&&a[i+1][j]==1&&a[i][j-1]==1&&a[i][j+1]==1)
                b[i][j]=1;
    fr(n)
    for(int j=1; j<=n; j++)
        if(b[i][j]&&vib[i][j]==0)
            dfsb(i,j);
    /*
    fr(n) {
        for(int j=1; j<=n; j++) cout<<vib[i][j]<<" ";
        cout<<endl;
    }//*/
    cout<<ca-cb<<endl;
    return 0;
}

by SvanurA @ 2023-01-16 23:11:56

解决了么？我的思路也是DFS

1. 先将不会被完全淹没的岛屿变成海洋，这样就不会参与到下面的统计
2. 这样一来，剩下的岛屿就全是能够完全被淹没的岛屿了

虽然我用的python而且还RE了两个，但还是希望能够给你带来一点思路

by Aakkosetsumussa @ 2023-01-30 11:18:07

@SvanurA 后来自己解决了，不过还是谢谢你提供思路 我自己用的思路是把岛屿用序号表上，淹后查找序号这样，就解决了那种恶心的情况

#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
typedef long double onr;
#define fr(y) for(inr i=1;i<=y;i++)
int n,a[1007][1007],b[1007][1007],ca=0,cnta=0,ans=0,via[1007][1007],v[100007];
char ch;
int dx[]= {0,1,-1,0, 0};
int dy[]= {0,0, 0,1,-1};
inline void dfsa(int x,int y) {
    if(via[x][y]==0) ca++,via[x][y]=++cnta;
    fr(4) {
        int tx=x+dx[i],ty=y+dy[i];
        if(a[tx][ty]==1&&1<tx&&tx<n&&1<ty&&ty<n&&!via[tx][ty]) {
            via[tx][ty]=via[x][y];
            dfsa(tx,ty);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    fr(n)
    for(int j=1; j<=n; j++) {
        cin>>ch;
        if(ch=='#') a[i][j]=1;
    }
    fr(n)
    for(int j=1; j<=n; j++)
        if(a[i][j]&&via[i][j]==0)
            dfsa(i,j);
    /*
    fr(n) {
        for(int j=1; j<=n; j++) cout<<via[i][j]<<" ";
        cout<<endl;
    }//*/
    fr(n)
    for(int j=1; j<=n; j++)
        if(a[i][j]==1)
            if(a[i-1][j]==1&&a[i+1][j]==1&&a[i][j-1]==1&&a[i][j+1]==1)
                b[i][j]=1;
    fr(n)
    for(int j=1; j<=n; j++)
        if(b[i][j]==1&&via[i][j]) v[via[i][j]]=1;
    fr(cnta) {
        ans+=(v[i]==1);
    }
    /*
    fr(n) {
        for(int j=1; j<=n; j++) cout<<vib[i][j]<<" ";
        cout<<endl;
    }//*/
    cout<<ca-ans<<endl;
    return 0;
}
/*
7
.......
..###..
..###..
...#...
..###..
..###..
.......
*/

最下面那几行，之前算一块，弄不好淹后就变两块了

by Etsuya233 @ 2023-08-12 16:33:32

谢谢！！！！