hzCPPOJ

数块(count)

时间限制:  1 s      内存限制:   128 MB
提交:21     正确:1     分值:100

题目描述

有⼀个n * n 的棋盘,每个格⼦有个坐标(x,y),(1 <=x,y<=n) 每个格⼦被染成了⿊⽩两种颜⾊之⼀。请你计算棋盘中⿊⾊联通块个数。
两个格⼦联通当且仅当他们有⼀条相同的边。

输入

输⼊⽂件有N+1 ⾏。第⼀⾏有⼀个整数n 表⽰棋盘的⻓和宽。

接下来n ⾏,每⾏有⼀个字符串。第i ⾏的字符串描述了棋盘第 i ⾏⿊⾊区域的信息。

每个区域都有⼀个数字 j,表⽰棋盘上(i,j)左边 的格⼦是⿊⾊。或者包含两个整数j,k,在字符串中表⽰为"j-k",表⽰第i⾏中[j,k] 列的部分都是⿊⾊。

这样描述的区域个数不会超过106个。

每⼀⾏字符串描述的两个区域之间会⽤','隔开,如果是最后⼀个区 域,会在后⾯加上⼀个分号';'。特殊的,如果某⼀⾏全是⽩⾊格 ⼦,那么描述这⾏的字符串只是";"。

举例说明,若棋盘⼤⼩为5,某⼀⾏字符串信息为"2,4-5;",它描述 的棋盘信息为:

⽩ ⿊ ⽩ ⿊ ⿊

输出

输出包括若⼲⾏,每⾏有两个整数s 和n , s表⽰联通块的⼤⼩, n表⽰所有联通块中,⼤⼩恰好为s 的联通块个数。

请按照联通块的⼤⼩,从⼤到⼩顺序输出。


样例

样例输入:
8 2,4-5; 5-6; 2-3,6; 6-7; ; 2-4; 2,4,6-7; 2-3,6-7;
样例输出:
7 2 4 1 2 1 1 1

提示

对于100% 的数据,1 <= n <= 30000
 

提交人

AmberXie

来源/分类