AcWing 1098. 城堡问题(dfs版)    原题链接    简单

作者： 作者的头像   小菜鸡UP ,  2020-04-16 18:23:37 ,  所有人可见 ,  阅读 860

1 


#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int const maxn=55;
int a[maxn][maxn];
int vis[maxn][maxn];
int rx,ry;
int ans=0;
int dfs(int x,int y)
{
    if(x>=1&&x<=rx&&y>=1&&y<=ry&&!vis[x][y])  
    {
        vis[x][y]=1;//怎么第一个点就一个if都没进直接到return res了 
        ///以后& |运算的时候加括号!!!!!!! 
        ans++;
        if( (a[x][y]&1)==0) dfs(x,y-1);
        if( (a[x][y]&2)==0) dfs(x-1,y);
        if( (a[x][y]&4)==0) dfs(x,y+1);
        if( (a[x][y]&8)==0) dfs(x+1,y);
    }
return ans;//这样是没法返回出来最终的res的 
}

int main(void)
{
    cin.tie(0);
    std::ios::sync_with_stdio(false);

    while(cin>>rx>>ry)
    {
      memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));
      int roomnum=0;int maxroom=0;  
      for(int i=1;i<=rx;i++)
        for(int j=1;j<=ry;j++)
            cin>>a[i][j];

      for(int i=1;i<=rx;i++)
        for(int j=1;j<=ry;j++)      
        {
            if(!vis[i][j])
            {
                roomnum++;
                ans=0;dfs(i,j);
                maxroom=max(ans,maxroom);       
            }
        }
      cout<<roomnum<<endl<<maxroom<<endl;;  
    }
return 0;   
}

4 评论

用户头像
dys   2020-05-24 11:04         踩      回复

###不知道哪里出了问题，请高数大佬帮忙看一下

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
char field[55][55];
int st[55][55];
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
int area=0;
void dfs(int x,int y){
    st[x][y]=1;
    for(int i=0;i<4;i++){
        int sx=x+dx[i];
        int sy=y+dy[i];
        if(sx>=0&&sx<n&&sy>=0&&sy<m&&!st[sx][sy]){
            if(!(field[sx][sy]>>i&1)){
                area++;
                dfs(sx,sy);
                st[sx][sy]=1;
            }
        }
    }
}
int main(){
    int res=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin>>field[i][j];
    }
    //int maxarea=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        if(!st[i][j]){
            dfs(i,j);
            area=max(area,0);
            res++;
        }
        cout<<res<<endl;
        cout<<area<<endl;
    return 0;
}
用户头像
小菜鸡UP   2020-05-24 17:22         踩      回复

阿下午在比赛，晚上有比赛.您找找抽风姐姐叭

用户头像
summerrr   2021-01-07 13:51         踩      回复 
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int field[55][55];
int st[55][55];
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
int area;
void dfs(int x,int y){
    st[x][y]=1;
    area++;
    for(int i=0;i<4;i++){
        int sx=x+dx[i];
        int sy=y+dy[i];
        if(sx<=0||sx>n||sy<=0||sy>m||st[sx][sy]) continue;
        if(field[x][y] >> i & 1) continue;
        dfs(sx,sy);
    }

}

int ans;
int main(){
    int res=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) 
        cin>>field[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(!st[i][j])
        {
            area=0;
            dfs(i,j);
            ans=max(area,ans);
            res++;
        }
        cout<<res<<endl;
        cout<<ans<<endl;
    return 0;
}
用户头像
summerrr   2021-01-07 13:52         踩      回复

帮你改了一下，可以AC了