题解 P1454 【圣诞夜的极光】

欢语_暗影 · 2018-04-06 10:38:37 · 题解

讲解：

这道题一看，各位读者就知道是DFS求连通图，水~，在此贴出DFS的代码和BFS的代码以及编者自己歪歪出的并查集代码。

代码实现： DFS:

#include<iostream>
using namespace std;
const int nx[13]={0,1,-1,0,0,2,-2,0,0,1,-1,1,-1};
const int ny[13]={0,0,0,1,-1,0,0,2,-2,-1,1,1,-1};//方向数组 
char a[1001][1001];
int n,m,ans;
void dfs(int x,int y)
{
    int i; 
    if(x<1 || x>n || y<1 || y>m || a[x][y]!='#') return;
    //越界或已走过就return 
    a[x][y]='-';//标记已走过 
    for(i=1;i<=12;i++) dfs(x+nx[i],y+ny[i]);
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j]; 
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if (a[i][j]=='#')
            {
                ans++;
                dfs(i,j);
            }
        }
    }
    cout<<ans;
}

BFS:

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
char a[101][101];
int book[101][101],n,m;
struct note{int x,y;};
void bfs(int x,int y)
{   
    int tx,ty,k;
    int next[12][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1},{-2,0},{0,-2},{0,2},{2,0}};
    queue<note>q;
    note z;
    q.push((note){x,y});
    book[x][y]=1;
    while(!q.empty())
    {   
        z=q.front();
        for(k=0;k<12;k++)
        {   
            tx=z.x+next[k][0];
            ty=z.y+next[k][1];
            if(tx<1||tx>n||ty<1||ty>m)  continue;
            if(a[tx][ty]=='#'&&book[tx][ty]==0)
            {   
                book[tx][ty]=1;
                q.push((note){tx,ty});
            }
        }
        q.pop();
    }
    return;
}
int main()
{   
    int i,j,ans=0;
    scanf("%d%d\n",&n,&m);
    //编者实测，没有\n你会wa（wrong answer） 
    for(i=1;i<=n;i++) gets(a[i]+1);//没有你会tle（超时） 
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]=='#'&&!book[i][j]) bfs(i,j),ans++;
    cout<<ans;    
}

并查集：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=110;
int a[inf][inf],n,m,ans,i,j,f[(inf+1)*(inf+1)];
int gets(int x)
{
    if(f[x]==x) return x;
    return f[x]=gets(f[x]);
}
void ff(int x,int y)
{
    int t1=gets(x),t2=gets(y);
    f[t1]=t2;
    return;
}
int main()
{
    char ch[inf];
    scanf("%d%d",&n,&m);
    for(i=1;i<=(n+1)*(inf+1)+(m+1);i++) f[i]=i;
    for(i=1;i<=n;i++)
    {
        scanf("%s",&ch);
        for(j=1;j<=m;j++)
        {
            if(ch[j-1]=='-') a[i][j]=0;
            else a[i][j]=1; 
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==0) continue;
            if(i-1>=1 && a[i-1][j]!=0) ff((i-1)*inf+j,i*inf+j);
            if(i-2>=1 && a[i-2][j]!=0) ff((i-2)*inf+j,i*inf+j);
            if(i+1<=n && a[i+1][j]!=0) ff((i+1)*inf+j,i*inf+j);
            if(i+2<=m && a[i+2][j]!=0) ff((i+2)*inf+j,i*inf+j);
            if(j-1>=1 && a[i][j-1]!=0) ff(i*inf+(j-1),i*inf+j);
            if(j-2>=1 && a[i][j-2]!=0) ff(i*inf+(j-2),i*inf+j);
            if(j+1<=m && a[i][j+1]!=0) ff(i*inf+(j+1),i*inf+j);
            if(j+2<=m && a[i][j+2]!=0) ff(i*inf+(j+2),i*inf+j);
            if(i-1>=1 && j-1>=1 && a[i-1][j-1]!=0) ff((i-1)*inf+(j-1),i*inf+j);
            if(i-1>=1 && j+1<=m && a[i-1][j+1]!=0) ff((i-1)*inf+(j+1),i*inf+j);
            if(i+1<=n && j-1>=1 && a[i+1][j-1]!=0) ff((i+1)*inf+(j-1),i*inf+j);
            if(i+1<=n && j+1<=m && a[i+1][j+1]!=0) ff((i+1)*inf+(j+1),i*inf+j);
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(f[i*inf+j]==i*inf+j && a[i][j]!=0) ans++;
    printf("%d",ans);
    return 0;
}