网页翻译用不了_企业排行榜_seo云优化软件破解版_如何建立一个自己的网站?

T1. 城堡问题

    1   2   3   4   5   6   7  #############################
1 #   |   #   |   #   |   |   ######---#####---#---#####---#
2 #   #   |   #   #   #   #   ##---#####---#####---#####---#
3 #   |   |   #   #   #   #   ##---#########---#####---#---#
4 #   #   |   |   |   |   #   ##############################

• # = Wall
• | = No wall
• - = No wall

上图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成 $m\times n(m\le 50,n\le 50)$ 个方块，每个方块可以有 $0\sim 4$ 面墙。

时间限制：1 s
内存限制：64 MB

• 输入
  程序从标准输入设备读入数据。
  第 $1$、$2$ 行每行 $1$ 个整数，分别是南北向、东西向的方块数。
  在接下来的输入行里，每个方块用一个数字 $(0\le p\le 50)$ 描述。用一个数字表示方块周围的墙，$1$ 表示西墙，$2$ 表示北墙，$4$ 表示东墙，$8$ 表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块 $(1,1)$ 的南墙同时也是方块 $(2,1)$ 的北墙。输入的数据保证城堡至少有两个房间。
• 输出
  输出 $2$ 行，每行一个数，表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
• 样例输入

  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
  

思路分析

此题考查基础搜索，属于基础题。

此题的难点在于输入格式，事实上，根据题目中每个方向墙的编号不难发现，每个格子中的数字某一个二进制位为 $1$，表明对应方向有墙。例如 $(11{)}_{10}=(1011{)}_2$，最高位的 $1$ 对应位权为 $8$，因此存在南墙，次高位的 $0$ 对应位权为 $4$，说明没有东墙。于是我们可以将方向增量按照西、北、东、南的顺序进行设置，当我们需要向第 $i$ 个方向搜索时，检测 a[x][y] & (1 << i) 是否为 $1$ 即可知晓是否有墙。

解决了这个问题之后，接下来就是求解连通块数量和最大连通块的面积，非常基础，此处不再赘述。

/** Name: T1.cpp* Problem: 城堡问题* Author: Teacher Gao.* Date&Time: 2025/02/08 15:29*/#include <iostream>using namespace std;int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};int n, m, cnt;
int a[55][55];
bool f[55][55];void DFS(int x, int y, int k) {for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if ((a[x][y] & (1 << i)) || f[nx][ny]) continue;f[nx][ny] = 1;cnt++;DFS(nx, ny, k);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];int tot = 0, ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (f[i][j]) continue;tot++, cnt = 1, f[i][j] = 1;DFS(i, j, tot);ans = ans