C++一本通 BFS The Castle 城堡

Question

原题在这

---

信息

语言 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;
}

Answer 1

修改看注释

 
#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;
}