Castle Room Analysis

Farmer John is back at his old Wisconsin castle and is eager to boast about it. Before he does, he needs to prepare by determining the number of rooms and the area of each room in his castle. The castle floor plan is divided into an \(n \times m\) grid, where each unit square may be enclosed by 0 to 4 walls. The outer boundary of the grid always has walls to protect against the elements.

In addition, Farmer John wants to remove exactly one wall (which separates two adjacent units) to combine two rooms into a new, larger room. In fact, there is one special wall such that removing it produces a room larger than any other possible removal.

You are given the floor plan of the castle. Each cell is described by an integer whose binary representation indicates the presence of walls using the following rules:

• 1: wall to the west
• 2: wall to the north
• 4: wall to the east
• 8: wall to the south

The task is to compute:

1. The total number of rooms.
2. The size of the largest room (in terms of number of unit squares) without removing any wall.
3. The size of the largest room obtainable by removing one wall.
</p>

Note: The castle is guaranteed to have at least 2 rooms and at least one removable wall.

Example: Consider a castle of 4 rows and 7 columns with the following grid (each number represents the walls in that unit):

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

This castle has 5 rooms with sizes 9, 7, 3, 1, and 8. Removing the special wall (as indicated in the annotated map) combines two rooms into a room of size 16, which is the maximum possible by removing a single wall.

inputFormat

The input begins with a line containing two positive integers \(n\) and \(m\) (the number of rows and columns, respectively). This is followed by \(n\) lines, each containing \(m\) integers. Each integer represents the wall configuration for that cell using the sum of the following values if a wall is present: west (1), north (2), east (4), and south (8). All border cells will have the appropriate outer walls.

Example 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

outputFormat

The output should consist of three lines:

1. The total number of rooms.
2. The size (number of unit squares) of the largest room without removing any wall.
3. The size of the largest room possible by removing exactly one wall.

Example Output:

5
9
16

sample

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
16

</p>