acwing1098. 城堡问题

题目

图1是一个城堡的地形图。

请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m∗n个方格区域，每个方格区域可以有0~4面墙。

注意：墙体厚度忽略不计。

题解

#include<iostream>
#define x first
#define y second
using namespace std;

typedef pair<int,int>PII;
const int N=55;
int m,n, g[N][N];
PII q[N*N];
bool st[N][N];
int bfs(int i,int j){
    int hh=0,tt=0;
    int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
    q[0]={i,j};
    int area=0;
    st[i][j]=true;
    while(hh<=tt){
        PII t=q[hh++];
        area++;
        for(int k=0;k<4;k++){
            int a=t.x+dx[k],b=t.y+dy[k];
            if(a<0||a>=n||b<0||b>=m)continue;
            if(st[a][b])continue;
            if(g[t.x][t.y]>>k&1)continue;
            q[++tt]={a,b};
            st[a][b]=true;
        }
    }
    return area;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    int area=0,cnt=0;
     for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(!st[i][j]){
                area=max(area,bfs(i,j));
                cnt++;
            }
    cout<<cnt<<endl;
    cout<<area<<endl;
    return 0;
}