只有十分的蒟蒻的提问
查看原帖
只有十分的蒟蒻的提问
174942
KLNG7楼主2020/5/26 20:50

dfs哪里有点问题?大佬们能帮看一下吗?dfs、bfs学的很不深,请大佬们指导一下。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,res,t,f;
char b[2005][20005];
int a[1000005],c[10005][10005],vis[10005][10005];
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,1,0,-1,1,-1,1,-1};
void dfs(int x,int y)
{
    if(x<1||x>n||y<1||y>m||vis[x][y]) return;
    t++;
    c[x][y]=1;
    for(int i=0;i<=7;i++)
    {
        if(b[x+dx[i]][y+dy[i]]=='*')
        {
            vis[x][y]=1;
            dfs(x+dx[i],y+dy[i]);
            vis[x][y]=0;
        }
        
    }
    
    
    
}
int main()
{
    freopen("star.in","r",stdin);
    freopen("star.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>b[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(b[i][j]=='*'&&!c[i][j])
            {
                dfs(i,j);
                a[++f]=t;
                t=0;
            }
            
        }
    }
    sort(a+1,a+f+1);
    for(int i=1;i<f;i++)
    {
        if(a[i]==a[i+1])
        {
            a[i+1]+=a[i];
            a[i]=0;
        }
    }
    for(int i=1;i<=f;i++)
    {
        if(a[i]) ans++;
        res=max(res,a[i]);
    }
    cout<<ans<<" "<<res;
    return 0;
}
2020/5/26 20:50
加载中...