AT_abc219_e [ABC219E] Moat

题目描述

在 $xy$ 平面上的若干点上有村庄。
高桥君为了保护这些村庄免受民兵、女巫等外敌的侵袭，打算建造一条能够包围所有村庄的护城河。

给定一个由 $0$ 和 $1$ 组成的 $4\times 4$ 矩阵 $A = (A_{i, j})$。
对于每一个满足 $A_{i, j} = 1$ 的整数对 $(i, j)$（$1 \leq i, j \leq 4$），在坐标 $(i-0.5, j-0.5)$ 处有一个村庄。

护城河是平面上的一个多边形。高桥君建造的护城河必须满足以下所有条件（也请参考输入样例1和输出样例1的说明）：

1. 不自交。
2. 内部包含所有村庄。
3. 所有顶点的 $x$ 坐标和 $y$ 坐标均为 $0$ 到 $4$ 之间的整数。
4. 所有边都平行于 $x$ 轴或 $y$ 轴。
5. 每个内角的度数为 $90$ 度或 $270$ 度。

请输出作为高桥君可以建造的护城河的方案数。

输入格式

输入以如下格式从标准输入读入：

$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$ $A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ $A_{2, 4}$ $A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ $A_{3, 4}$ $A_{4, 1}$ $A_{4, 2}$ $A_{4, 3}$ $A_{4, 4}$

输出格式

请输出高桥君可以建造的护城河的方案数。

输入输出样例 #1

输入 #1

1 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

输出 #1

1272

输入输出样例 #2

输入 #2

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出 #2

1

说明/提示

限制条件

• $A_{i, j} \in \{0, 1\}$
• 至少存在一个 $(i, j)$ 使得 $A_{i, j} = 1$

样例说明 1

下列两张图片中的例子，均满足高桥君建造护城河的条件。

下列四张图片中的例子，不满足高桥君建造护城河的条件。

上述四个例子不满足高桥君建造护城河的条件的理由如下：

• 第一张图片不满足“不自交”这一条件。
• 第二张图片不满足“内部包含所有村庄”这一条件。
• 第三张图片不满足“所有顶点的 $x$ 坐标和 $y$ 坐标均为 $0$ 到 $4$ 之间的整数”这一条件（存在顶点坐标不是整数）。
• 第四张图片不满足“所有边都平行于 $x$ 轴或 $y$ 轴”这一条件。

由 ChatGPT 4.1 翻译