#403. 城堡问题

城堡问题

城堡问题

题目描述

下图是一座城堡的地形图。每个方格可能有 0 到 4 面墙,墙体厚度忽略不计。

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

方向规定为上北、下南、左西、右东。城堡被划分为 m×nm\times n 个方格区域。没有墙阻挡的相邻方格属于同一个房间。

请你编写程序,计算:

  1. 城堡共有多少个房间;
  2. 面积最大的房间有多少个方格。

每个方格用一个整数 PP 表示其四面墙的情况,采用以下位权:

  • 1:西墙;
  • 2:北墙;
  • 4:东墙;
  • 8:南墙。

PP 等于该方格所有墙对应数字的总和。例如,P=3=1+2P=3=1+2 表示有西墙和北墙。

相邻方格之间的同一面墙会在两个方格的描述中各记录一次。例如,方格 (1,1)(1,1) 的南墙也是方格 (2,1)(2,1) 的北墙。

输入保证至少存在两个房间。

输入格式

第一行输入两个整数 m,nm,n,分别表示南北方向的方格数和东西方向的方格数。

接下来 mm 行,每行 nn 个整数,表示对应方格的墙特征 PP。

输出格式

输出两行:第一行为房间总数,第二行为最大房间的面积(以方格数计)。

数据范围

1≤m,n≤501\le m,n\le 50,0≤P≤150\le P\le 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

提示

只能通过没有墙的 上下左右四个方向 移动,斜对角接触不算连通。可以使用 P & 1、P & 2、P & 4、P & 8 检查对应方向是否有墙。