The Castle

Problem Background

Special for beginners, ^_^

Problem Description

A castle is divided into an $m \times n$ grid of cells ($m \le 50, n \le 50$). Each cell may have $0$ to $4$ walls ($0$ means no wall). The floor plan is shown below:

The thick black lines in the picture are walls. Several connected cells form a room, and rooms are always separated from each other by black lines (walls).

Write a program that answers these two questions:

1. How many rooms are there in the castle?
2. What is the area (number of cells) of the largest room?

Input Format

Each cell of the plan is described by a single number (the first cell, for example, is represented in binary as 1011, meaning "no east wall", which is decimal 11).

The first line contains one integer $m$ ($m \le 50$): the length of the castle from south to north.

The second line contains one integer $n$ ($n \le 50$): the length from east to west.

The following $m$ lines each contain $n$ integers, describing the cells of the plan row by row. The walls of a cell are encoded by a number $P$ ($0 \le P \le 15$), which is the sum of the following values:

• $1$ — west wall
• $2$ — north wall
• $4$ — east wall
• $8$ — south wall

Interior walls are defined twice: for example, the south wall of cell $(1, 1)$ is also defined once by cell $(2, 1)$ to its south.

There are at least two rooms in the castle.

Output Format

The first line: one integer, the total number of rooms.

The second line: one integer, the area (number of cells) of the largest room.

Sample Input

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

Sample Output

5
9

Constraints

$m \le 50,\ n \le 50$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• Flood-fill each connected region: start from an unvisited cell, traverse through all cells reachable without crossing a wall, and mark them as one room.
• To test whether you can move from a cell in a given direction, check the corresponding bit of $P$ (and its neighbour's bit for shared walls).