船只 - 题目

“Ships” 游戏的棋盘由 $N \times N$ 的方格组成。每个方格可能属于某艘船，也可能是空的。如果两个属于船只的方格有公共边，则这两个方格属于同一艘船。不同船只的方格没有公共点（即不能共用边或顶点）。船只的吨位（Tonnage）是属于该船只的方格数量。

在给定的例子中，属于船只的方格被标记为黑色。棋盘上共有：一艘 29 吨的船、三艘 7 吨的船、两艘 4 吨的船和三艘 1 吨的船。

编写一个程序，根据给定的棋盘描述，计算船只的数量以及每艘船的吨位。

输入第一行包含一个正整数 $N$（$N < 30000$）。

接下来的 $N$ 行中，每行给出棋盘中一行（从左到右）的信息，依次描述属于船只的方格组。每个方格组采用以下两种格式之一：

<number_of_square_column>：如果给定列的方格属于船只，而其左侧和右侧的方格都是空的；
<number_of_first_square_column>-<number_of_last_square_column>：如果从起始列到结束列（含）的所有连续方格都属于船只，且该组左侧和右侧的方格都是空的。

方格组之间用逗号（,）分隔，每行以分号（;）结尾。行中不包含空格。如果棋盘的某一行中没有属于船只的方格，则对应的行仅包含一个分号。已知船只的总数不超过 $1000$，且任何船只的吨位不超过 $1000$ 吨。

输出关于船只的信息。每行应包含两个由空格隔开的整数。第一个整数为吨位，第二个整数为具有该吨位的船只数量。吨位必须按降序排列输出，且只有当存在至少一艘该吨位的船只时才输出。

12
2-4,7,9;
1,4,11-12;
1,4,10,12;
1,4-8,10-12;
1,8;
1,3-6,8,10-12;
1,3,5-6,8,11;
1,8,10-12;
1-8;
;
2;
2-4,7-10,12;

QOJ.ac