spoj#UCV2013H. Slick

Slick

以下题面由 AI 翻译。

题目描述

一场海上事故导致菲利普斯坦尼亚(Felipistonia)海域发生原油泄漏,这引发了重大自然灾害。菲利普斯坦尼亚政府希望在事态恶化前清理油污。为此,他们首先需要评估事故的严重程度及泄漏的原油总量。政府唯一可用的评估工具是通过卫星图像估算清理费用。利用这些图像,他们需确定海面上油膜(slick)的数量及每个油膜的大小。油膜指漂浮在水面上的原油块。由于政府人员能力有限,他们雇佣你协助处理图像。

图1(a)展示了卫星获取的示例图像,图1(b)将其转换为由0和1组成的矩阵。给定该二进制矩阵,你的任务是统计海洋中的油膜数量及其对应大小。若两个相邻像素(上下或左右相邻)同为1,则视为同一油膜。

(a) 原油泄漏的卫星图像 (b) 二进制矩阵表示的图像

图1: (a) 原油泄漏的卫星图像 (b) 二进制矩阵表示的图像

输入格式

输入包含多个测试用例,每个用例对应不同的卫星图像。每个用例的第一行为两个整数,表示图像的行数(N)和列数(M)(1 ≤ N, M ≤ 250)。接下来N行,每行包含M个整数,表示图像数据。

输入以一行N = M = 0结束,该用例无需处理。

输出格式

对于每个图像,首先输出油膜的总数。随后按油膜大小升序输出每个大小及其对应的油膜数量,格式为大小 数量,每行一个条目。

样例数据

输入:

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

输出:

7
1 2
2 1
6 1
10 2
20 1

数据范围

  • 1 ≤ N, M ≤ 250