#403. 城堡问题
城堡问题
城堡问题
题目描述
下图是一座城堡的地形图。每个方格可能有 0 到 4 面墙,墙体厚度忽略不计。
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
方向规定为上北、下南、左西、右东。城堡被划分为 个方格区域。没有墙阻挡的相邻方格属于同一个房间。
请你编写程序,计算:
- 城堡共有多少个房间;
- 面积最大的房间有多少个方格。
每个方格用一个整数 表示其四面墙的情况,采用以下位权:
1:西墙;2:北墙;4:东墙;8:南墙。
等于该方格所有墙对应数字的总和。例如, 表示有西墙和北墙。
相邻方格之间的同一面墙会在两个方格的描述中各记录一次。例如,方格 的南墙也是方格 的北墙。
输入保证至少存在两个房间。
输入格式
第一行输入两个整数 ,分别表示南北方向的方格数和东西方向的方格数。
接下来 行,每行 个整数,表示对应方格的墙特征 。
输出格式
输出两行:第一行为房间总数,第二行为最大房间的面积(以方格数计)。
数据范围
,。
输入样例
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
提示
只能通过没有墙的 上下左右四个方向 移动,斜对角接触不算连通。可以使用 P & 1、P & 2、P & 4、P & 8 检查对应方向是否有墙。