← 返回题目列表

Codeforces · 178/E1

E1. 海狸的问题 - 2

中文机器翻译题面 查看原题

向 ABBYY Cup 参与者提供由 Smart Beaver 编写的问题正在成为一种传统。他提出了以下问题。

给您一个单色图像,即由两种颜色(黑色和白色)组成的图像。图像以光栅形式给出,即作为像素颜色的矩阵,并且矩阵的大小与图像的大小一致。

给定图像上的白色对应于背景。此外,图像包含几个黑色几何形状。众所周知,图像只能包含两种形状:正方形和圆形。您的任务是计算给定图像包含的圆圈数和正方形数。

图像上的方块可以任意旋转。另外,图像可能包含一些噪声,其排列如下:原始图像的每个像素可以以20%的概率将其颜色改变为相反的颜色。

没有噪声且正方形边与坐标轴平行的图像示例(两个圆形和三个正方形)。

没有噪声且正方形任意旋转(两个圆形和三个正方形)的图像示例。

具有噪声且正方形任意旋转(一个圆形和三个正方形)的图像示例。

输入

第一个输入行包含一个整数 n (1000 ≤ n ≤ 2000),它是原始图像的长度和宽度。

接下来的 n 行描述了图像像素的颜色矩阵。第 i 行恰好包含 n 个整数 aij (0 ≤ aij ≤ 1),每个整数之间用空格分隔。 aij = 0 的值对应于白色像素,aij = 1 对应于黑色像素。

保证图像中正方形的边长和圆形的直径至少为15个像素,且任意两个图形之间的距离至少为10个像素。它还保证人类可以轻松计算原始图像中的圆形和正方形的数量。图像中的人物总数不超过50个。

获得 20 点的输入限制为:

- 这些测试用例没有噪声,并且正方形的边平行于坐标轴。

获得 50 点的输入限制为:

- 这些测试用例没有噪音,但方块被任意旋转。

获得 100 点的输入限制为:

- 这些测试用例有噪声并且方块被任意旋转。

输出

恰好打印两个整数,并用一个空格分隔 - 相应地,给定图像中的圆圈数和正方形数。

注意

您将获得每个难度级别的原始数据样本。这些示例可从 http://codeforces.com/static/materials/contests/178/e-samples.zip 获取。