一只姓梁的monkey 2023-01-02 16:25 采纳率: 53.8%
浏览 36
已结题

C++一本通 BFS The Castle 城堡

原题在这


信息

语言 C++
算法 BFS
问题 测试点2 测试点7 答案错误,其余(包括 原题数据和自设数据)均可通过


代码


#include<iostream>
#include<cstdio>
using namespace std;
int n,m,F[4][2]={{0,-1},{-1,0},{0,1},{1,0}},T,W,Room_sum,Room_max;
struct Node
{
    int x,y,wall[4],B;
}map[55][55],Q[100001],S,L;
void print()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout<<map[i][j].B;
        }
        cout<<endl;
    }
}
int BFS()
{
    int sum=0;
    T=1;
    W=0;
    W++;
    Q[W]=S;
    while(T<=W)
    {
        S=Q[T];
        L=S; 
        T++; 
        for(int i=0;i<4;i++)
        {
            S.x+=F[i][0];
            S.y+=F[i][1];
            if(S.x>=0 && S.x<n && S.y>=0 && S.y<m && map[S.x][S.y].B==0 && map[L.x][L.y].wall[i]==0)
            {
                sum++;
                W++;
                Q[W]=S;
                map[S.x][S.y].B=1;
            }
            S.x-=F[i][0];
            S.y-=F[i][1];
        }
    }
    return sum;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int w;
            cin>>w;
            map[i][j].wall[3]=(w>=8);
            w-=map[i][j].wall[3]*8;
            map[i][j].wall[2]=(w>=4);
            w-=map[i][j].wall[2]*4;
            map[i][j].wall[1]=(w>=2);
            w-=map[i][j].wall[1]*2;
            map[i][j].wall[0]=(w>=1);
            w-=map[i][j].wall[0]*1;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(map[i][j].B==0)
            {
                int x;
                Room_sum++;
                S.x=i;
                S.y=j;
                x=BFS();
                Room_max=(x>Room_max?x:Room_max);
            }
        }
    }
    cout<<Room_sum<<endl<<Room_max;
}
  • 写回答

1条回答 默认 最新

  • bekote 2023-01-04 11:28
    关注

    修改看注释

    
     
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,m,F[4][2]={{0,-1},{-1,0},{0,1},{1,0}},T,W,Room_sum,Room_max;
    struct Node
    {
        int x,y,wall[4],B;
    }map[55][55],Q[100001],S,L;
    void print()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cout<<map[i][j].B;
            }
            cout<<endl;
        }
    }
    int BFS()
    {
        //int sum=0; 当四周都是墙时,房间大小至少为1
        int sum=1;
        T=1;
        W=0;
        W++;
        Q[W]=S;
        while(T<=W)
        {
            S=Q[T];
            L=S; 
            T++; 
            //标记起点
            map[S.x][S.y].B=1;
            for(int i=0;i<4;i++)
            {
                S.x+=F[i][0];
                S.y+=F[i][1];
                if(S.x>=0 && S.x<n && S.y>=0 && S.y<m && map[S.x][S.y].B==0 && map[L.x][L.y].wall[i]==0)
                {
                    sum++;
                    W++;
                    Q[W]=S;
                    map[S.x][S.y].B=1;
                }
                S.x-=F[i][0];
                S.y-=F[i][1];
            }
        }
        return sum;
    }
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int w;
                cin>>w;
                map[i][j].wall[3]=(w>=8);
                w-=map[i][j].wall[3]*8;
                map[i][j].wall[2]=(w>=4);
                w-=map[i][j].wall[2]*4;
                map[i][j].wall[1]=(w>=2);
                w-=map[i][j].wall[1]*2;
                map[i][j].wall[0]=(w>=1);
                w-=map[i][j].wall[0]*1;
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(map[i][j].B==0)
                {
                    int x;
                    Room_sum++;
                    S.x=i;
                    S.y=j;
                    x=BFS();
                    Room_max=(x>Room_max?x:Room_max);
                }
            }
        }
        cout<<Room_sum<<endl<<Room_max;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 1月4日
  • 已采纳回答 1月4日
  • 创建了问题 1月2日

悬赏问题

  • ¥15 我需要全国每个城市的最新小区名字等数据。
  • ¥15 开发一个小区生态的小程序
  • ¥15 MddBootstrapInitialize2失败
  • ¥15 LCD Flicker
  • ¥15 Spring MVC项目,访问不到相应的控制器方法
  • ¥15 esp32在micropython环境下使用ssl/tls连接mqtt服务器出现以下报错Connected on 192.168.154.223发生意外错误: 5无法连接到 MQTT 代理,如何解决?
  • ¥15 关于#genesiscsheel#的问题,如何解决?
  • ¥15 Android aidl for hal
  • ¥15 STM32CubeIDE下载程序报错
  • ¥15 微信好友如何转变为会员系统?(相关搜索:小程序)