UCV2013H - Slick


A maritime accident has caused oil to spill onto the seas of Felipistonia, which is a major natural disaster. The Felipistonia's government wants to clean up this mess before more damage occurs. To do this, they first have to know how serious was the accident and the amount of oil that has been spilled into the sea. The only instrument the Felipistonia's government has to get information of the magnitude of this disaster, is the use of satellite images. With these images they can estimate how much money they have to spend to clean this mess. For this, the number of slicks in the seas and the size of each slick must be know. A slick is a patch of oil floating on water. Unfortunately, the Felipistonia's people are not very bright, so they have hired you to help them process the image.

An example of an image obtained by the satellites is shown in Figure 1(a). This image can be transformed to 0's and 1's as seen in Figure 1(b). Given this binary matrix, your job is to count the number of slicks in the ocean and their corresponding size. Two adjacent pixels in the image are considered to be in the same slick if they are in the same row or the same column.

(a) A satellite image of the spilled oil. (b) The representation of the image in a binary matrix

Figure 1: (a) A satellite image of the spilled oil. (b) The representation of the image in a binary matrix

Input

The input contains several test cases, each one corresponding to a different satellite image. The first line of each case contains two integers that indicate the number of rows (N) and columns (M) in the image (1 <= N, M <= 250). Then N lines follows with M integers each, containing the information of the image.

The end of input is indicated by a test case with N = M = 0. This case should not be processed.

Output

For each image, output the number of slicks in the sea. Additionally, output the size of each slick in ascending order and the number of slicks of that size.

Example

Input:
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 1 1 1
1 1 0 0 1 0 0 1 1 1
1 0 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0

Output:
7
1 2
2 1
6 1
10 2
20 1

hide comments
:.Mohib.:: 2015-10-20 17:52:14

well framed..!!

Utkarsh Rastogi: 2014-12-30 12:20:57

not printing total number of slicks caused me 1 WA...

Mitch Schwartz: 2014-10-03 22:11:42

@mayank: Your claim that "if you are reading the comments, then you are looking for hints" is not true and is somewhat disturbing. The fact that spoiling comments sometimes (or maybe often) go uncensored does not make it ok to leave them. Unfortunately, moderating comments is a very time consuming job, and nobody is getting paid to do it. Of course some spoilers are more serious than others, and I usually only take care of the more serious cases. (Incidentally, the comments on Polish SPOJ are better moderated than here, and I think we could learn from that example.)

Some examples of valuable comments: (1) clarifying ambiguous wording in the problem statement, (2) specifying missing constraints, (3) linking to a harder variant of the problem that users may want to try afterward, (4) saying thank you for a very enjoyable problem, (5) reporting that the input is not well formatted.

Examples of comments that should generally not appear: (1) asking for hints, (2) asking for extra test cases, (3) telling people how to solve the problem, (4) a link to your buggy code, (5) a link to your AC code, (6) information that is not useful to anyone ("AC in the first attempt" generally falls into this category, unless maybe it's a super-hard problem), (7) asking the author to help you debug your code when you have not demonstrated a reasonable effort to debug it yourself.

I write that these comments should generally not appear because there are some exceptions. For example, sometimes a good way to ask for clarification is to pick a trivial test case and give two possible answers (depending on two different interpretations) and ask which is the expected answer. Also, sometimes relatively vague hints are ok (but that can be hard to judge, so it is not recommended in general).

It is my hope that eventually people will catch on to such notions without needing to be told.

Note that the forum is an appropriate place to discuss debugging and related issues. Please be sure to read the forum guidelines as described by TripleM and Leppy before posting there.

Last edit: 2014-10-04 02:13:05
mayank: 2014-10-03 19:28:23

dfs and maps! :D PS> Sorry, but if you are reading the comments, then you are looking for hints. :P

Anubhav Balodhi : 2014-07-31 19:46:21

It took a lot of time to debug the naive recursive solution...

Sumit Mishra: 2014-06-05 11:11:43

http://ideone.com/7nLZPz
wrong answer!!!

Prateek chandan: 2013-09-19 14:46:36

I checked all the test case on my computer but still WA
Please look it 10075243
Is there any tricky case which i am missing ?

Adam D: 2013-08-28 17:02:14

What is output for
5 5
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 0

Last edit: 2013-09-02 17:29:16
Mostafa 36a2: 2013-07-27 11:56:12

@Chandan Singh
0

Last edit: 2013-07-27 11:57:51
Chandan Singh: 2013-07-27 10:09:34

what would be output of
1 1
0


Added by:Hector Navarro
Date:2013-07-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Francisco Sans