P4380 [USACO18OPEN] Multiplayer Moo S

The cows have invented a new game, and surprisingly, they gave it the least creative name: "Moo". The Moo game is played on a board consisting of $N \times N$ square cells. A cow can claim a cell by shouting "Moo!" and then writing her numeric ID in that cell. At the end of the game, each cell contains a number. At that point, if a cow has created a region of connected cells and that region is at least as large as every other region, then that cow wins. A "region" is defined as a set of cells with the same numeric ID, where each cell is directly adjacent (up, down, left, or right) to another cell in the same region (diagonals do not count). Since playing solo can be a bit boring, the cows are also interested in playing in two-cow teams. Two cows on the same team can form a region, but now the cells in the region may belong to either cow on the team. Given the final state of the game board, please help the cows compute: 1. The number of cells in the largest region owned by any single cow. 2. The number of cells in the largest region owned by any team of two cows. Note that a region owned by two cows must contain IDs from both cows on the team; it cannot contain only one cow’s ID.

The first line contains $N$ ($1 \leq N \leq 250$). Each of the next $N$ lines contains $N$ integers (each in the range $0 \ldots 10^6$), describing the final state of the board. The board contains at least two distinct numbers.

Output two lines: the first line is the size of the largest region owned by any single cow, and the second line is the size of the largest region owned by any two-cow team.

In this example, the largest single-cow region consists of five $9$s. If cows with IDs $1$ and $9$ form a team, they can form a region of size $10$. Problem by: Brian Dean. Translated by ChatGPT 5