Problem1033--拆字游戏

1033: 拆字游戏

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 433  Solved: 144
[Submit] [Status] [Web Board] [Creator:]

Description

PiPi喜欢把别人的名字拆开来,比如“螺”就可以拆成“虫田糸”,PiPi的语文学的不是很好,于是她决定使用编程的方式来解决这个问题。

给出一个01矩阵,1占据的部分即为需要拆的字,如果两个1分享一条边,那么它们连通。连通具有传递性,即如果a、b连通,b、c连通,则a、c连通。

连通的一系列1被看做可以拆出的一块,现在PiPi需要输出这些拆出的块(用一个01矩阵表示,并且要求矩阵的大小尽可能的小)。

为了确保输出的顺序尽可能的和书写的顺序一致,PiPi从每个块中选出最左上角的点(最左侧的点中,最靠上的)作为代表点,然后按照代表点从左到右(若相同则按从上到下)的顺序输出所有拆出的块。

Input

多组数据。

输入的第一行为两个正整数N、M,表示01矩阵的大小。

接下来N行,每行M个01字符,描述一个需要拆的字。

对于40%的数据,满足1<=N,M<=10。

对于100%的数据,满足1<=N,M<=500。

额外的样例:

11 17
00000000000000000
00001111111100000
00000000000000000
00111111111111100
00000000100000000
00000010101110000
00000110100011000
00011100100001000
00000010100000000
00000001100000000
00000000000000000

Output

按照代表点从左到右(若相同则按从上到下)的顺序输出所有拆出的块。

对于每个块,先输出其大小,然后用对应的01矩阵表示这个块。

7 13
1111111111111
0000001000000
0000001000000
0000001000000
0000001000000
0000001000000
0000011000000
3 4
0001
0011
1110
1 8
11111111
1 1
1
3 4
1110
0011
0001

Sample Input

14 22
0000000000001111111100
0000000000001101101100
0000110000001111111100
0000110000001101101100
0111111110001111111100
0110110110000000000000
0110110110000011000000
0111111110001111111000
0000110000000001100000
0000110110001111111100
0111111111000111111000
0000000010001101101100
0000000000000001100000
0000000000000011100000

Sample Output

10 9
000110000
000110000
111111110
110110110
110110110
111111110
000110000
000110110
111111111
000000010
5 8
11111111
11011011
11111111
11011011
11111111
8 8
00110000
11111110
00011000
11111111
01111110
11011011
00011000
00111000

HINT

PIPI:大家还记得联通分量这个概念吧~

Source/Category

中等    搜索