P5962 [BalticOI 2004] Ships (Day1)

There is a “ships” game board consisting of an $n \times n$ grid of square cells. Each cell may belong to some ship (black) or be empty. If two edge-adjacent cells are both black, then these two cells belong to the same ship. Different ships do not share an edge. The tonnage of a ship is the number of such connected adjacent cells. In the given example, the black cells on the board belong to ships: there is one $29$-ton ship, three $7$-ton ships, two $4$-ton ships, and three $1$-ton ships.  Write a program that, for a given game position, computes the tonnage and the count of ships of each tonnage.

The first line contains an integer $n$, the size of the game board. In the next $n$ lines, line $i+1$ describes the columns (ships) information of row $i$, separated by commas: - If it is a single number, then that column belongs to a ship, and the left and right cells in that row are empty. - If it is two numbers connected by `-`, then all cells between these two columns (including them) belong to a ship, and the cells to the left and right are empty. The data are separated by commas, and each line ends with a semicolon. There are no spaces in a line. If a line contains only a semicolon, then this row has no ship information.

Your program must output the ship information. Each line contains two integers separated by a space. The first number is the ship tonnage, and the second number is the number of ships with that tonnage. You must output ship tonnages in decreasing order, and only tonnages that occur at least once.

For all testdata, $1 \le n < 3 \times 10^4$. Both the total number of ships and the ship tonnages do not exceed $10^3$. Translated by ChatGPT 5