P1457 [USACO2.1] The Castle

Our honest USACO protagonist, Farmer John, received a special birthday gift with unbelievable luck: a “Lucky Ireland” lottery ticket. It won him the only prize of the contest — a dreamlike castle located in the Irish countryside!

Boastful Farmer John immediately returned to his hometown in Wisconsin, where boasting is a tradition, to brag about everything regarding his castle. He needs to prepare before boasting: for example, how many rooms the castle has and how large each room is. In addition, Farmer John wants to remove a single wall (a wall between two unit squares) to form a larger room. Your job is to help him prepare by computing the number of rooms and the size of each room. The castle floor plan is divided into $n \times m$ unit squares. Each unit square may have $0 \sim 4$ surrounding walls. The entire castle is enclosed by exterior walls to keep out wind and rain. (That is, the outer boundary of the floor plan is certainly walled.) Please study carefully the annotated floor plan of a castle below: ```plain 1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # -># | | | | # # ############################# ``` - $\verb!#!$ denotes a wall. - $\verb!|!$ and $\verb!-!$ denote the absence of a wall. - $\verb!->!$ points to a wall; removing this wall yields the largest possible new room. A friendly reminder: this castle floor plan has $4 \times 7$ unit squares. A “room” is a maximal set of unit squares connected through openings (i.e., adjacent squares without a wall between them). For example, this sample has $5$ rooms (with sizes $9,7,3,1,8$ units, in no particular order). Removing the wall indicated by the arrow merges $2$ rooms into one new room that is larger than any room obtained by removing any other single wall. The castle is guaranteed to have at least $2$ rooms, and there is always at least one wall that can be removed.

The first line contains two positive integers $m,n$, meaning the castle has $n$ rows and $m$ columns. The next $n$ lines each contain $m$ integers. Each integer for a unit square tells whether there are walls to its west, north, east, and south. Each number is the sum of any subset of the following four integers: $1$: a wall to the west. $2$: a wall to the north. $4$: a wall to the east. $8$: a wall to the south. Interior walls are specified twice. For example, the south wall of $(1,1)$ is also specified as the north wall of $(2,1)$.

Output four lines: - The first line: the number of rooms in the castle. - The second line: the size of the largest room. - The third line: the largest room size obtainable by removing one wall. - The fourth line: which wall to remove to obtain the largest possible new room. Choose the best wall to remove. If there are multiple choices, pick the westernmost one. If there is still a tie, pick the southernmost one. For the same cell, prefer the north wall over the east wall. Represent the wall by outputting the row number, column number, and the wall’s direction ($N$ for north or $E$ for east). That is, identify a wall by the cell whose north or east wall is to be removed.

Constraints For $100\%$ of the testdata, $1 \le n,m \le 50$. USACO 2.1 Translated from NOCOW. Translated by ChatGPT 5