[BalticOI 2004] ships 船
题目描述
有一个由 $n\times n$ 的正方形组成的“船”的游戏棋盘。每个单元格可能属于某艘船(黑色)或为空。如果两个边相邻的单元格都是黑色,那么这两个单元格属于同一艘船。不同船之间没有公共边。船的吨位是这些相邻的单元格数。
下边样例,棋盘中(黑色)的单元格属于船,共有一艘 $29$ 吨的船,三艘 $7$ 吨的船,二艘 $4$ 吨的船,三艘 $1$ 吨的船。
![样例](https://cdn.luogu.com.cn/upload/image_hosting/uk57lz80.png?x-oss-process=image/resize,m_lfit,h_170,w_225)
请写一个程序,对给定的游戏棋盘计算出每艘船的吨位和数量。
输入输出格式
输入格式
第一行包含一个整数 $n$ 表示游戏棋盘的大小。
以下 $n$ 行,第 $i+1$ 行描述第 $i$ 行的列(船)的信息,中间用一个逗号分隔:
如果是单独一个数,那么这一列属于船,这列的左、右单元格是空的;
如果是```-```连接的两个数,表示这两列之间的所有格子(包含这两列)都属于船,则左侧和右侧是空的。
数据之间用逗号分隔,每行结尾的分号。行中没有空格。如果某行只有一个分号,则这行没有船的信息。
输出格式
你的程序必须输出船的信息。每行是一个空格分隔的两个整数。第一个数是船的吨位,第二个数是这个吨位的船只数量。必须以递减顺序输出船的吨位,并且至少有一艘船有此吨位。
输入输出样例
输入样例 #1
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;
输出样例 #1
29 1
7 3
4 2
1 3
说明
对于所有的数据,$1\le n\le 3\times 10^4$,船舶总数和船舶吨位都不超过 $10^3$。