AcWing 1098. 城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####—#####—#---#####—#
2 # # | # # # # #
#—#####—#####—#####—#
3 # | | # # # # #
#—#########—#####—#---#
4 # # | | | | # #
#############################
(图 1)
= Wall
| = No wall
- = No wall
方向：上北下南左西右东。
图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 m?n个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。
输入格式
第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。
例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围
1≤m,n≤50,
0≤P≤15
输入样例：
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
输出样例：
5
9
这道题还是比较难想的，这道题运用了二进制于方向结合的方法，因为墙有点类似于二进制，我们把它看作是否可以向某个方向移动的条件，于是我们将其和dx，dy（下一步走的方向结合起来）然后求解。
代码如下：
#include<iostream>
#include<queue>using namespace std;const int N=55;typedef pair<int,int> PII;int g[N][N];
bool st[N][N];
int n,m; int dx[4]={
0,-1,0,1}; int dy[4]={
-1,0,1,0};
int cnt=0;void bfs(int sx,int sy)
{
queue<PII> q;q.push({
sx,sy});st[sx][sy]=true;int ans=1;while(q.size()){
auto t=q.front();q.pop();int id=g[t.first][t.second];// cout<<t.first<<" "<<t.second<<endl;for(int i=0;i<4;i++)if(!(id>>i&1)){
int tx=t.first+dx[i];int ty=t.second+dy[i];if(tx<1||ty<1||tx>n||ty>m||st[tx][ty])continue;// cout<< "tx"<<tx<<" "<<ty<<" "<<i<<endl;st[tx][ty]=true;q.push({
tx,ty});ans++;}}cnt=max(ans,cnt);
}
int main(void)
{
cin>>n>>m;int res=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!st[i][j])bfs(i,j),res++;cout<<res<<endl<<cnt;
}