CF178E2 The Beaver's Problem - 2

为 ABBYY Cup 参赛者提供由 Smart Beaver 编写的题目已成为一种传统。他提出了如下问题。 给定一张单色图像，即由两种颜色（黑色和白色）组成的图像。图像以光栅形式给出，即以像素颜色矩阵的形式给出，矩阵的大小与图像的大小一致。 图像中的白色表示背景。此外，图像中包含若干黑色几何图形。已知图像中只包含两种类型的图形：正方形和圆形。你的任务是统计图像中圆形和正方形的数量。 图像中的正方形可以任意旋转。此外，图像中可能存在如下形式的噪声：原始图像的每个像素都有 $20\%$ 的概率将其颜色反转。  无噪声且正方形边与坐标轴平行的图像示例（两个圆形和三个正方形）。  无噪声且正方形任意旋转的图像示例（两个圆形和三个正方形）。  有噪声且正方形任意旋转的图像示例（一个圆形和三个正方形）。

第一行包含一个整数 $n$（$1000 \leq n \leq 2000$），表示原始图像的长和宽。 接下来的 $n$ 行描述图像像素颜色的矩阵。第 $i$ 行包含恰好 $n$ 个整数 $a_{ij}$（$0 \leq a_{ij} \leq 1$），用空格分隔。$a_{ij}=0$ 表示白色像素，$a_{ij}=1$ 表示黑色像素。 保证图像中正方形的边长和圆的直径至少为 15 像素，任意两个图形之间的距离至少为 10 像素。还保证人类可以轻松计算原始图像中圆形和正方形的数量。图像中的图形总数不超过 50。 获得 20 分的输入限制： - 这些测试点没有噪声，且正方形的边与坐标轴平行。 获得 50 分的输入限制： - 这些测试点没有噪声，但正方形可以任意旋转。 获得 100 分的输入限制： - 这些测试点有噪声，且正方形可以任意旋转。

输出恰好两个整数，用一个空格隔开，分别表示图像中圆形和正方形的数量。

每个难度级别的原始数据样例可在 http://codeforces.ru/static/materials/contests/178/e-samples.zip 下载。 由 ChatGPT 4.1 翻译