Score : $500$ points

问题描述

在 $xy$ 平面上有一些点，代表了一些村庄的位置。
高桥将要构建一条护城河来保护这些村庄免受敌人的侵袭，比如民间军队和女巫。

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

护城河将在平面上形成一个多边形。高桥将按照以下条件来建造它。（参见示例输入/输出 1 的注释部分。）

1. 没有自相交。
2. 所有村庄都在多边形内部。
3. 每个顶点的 $x$ 和 $y$ 坐标都是整数，范围在 $0$ 到 $4$（包含）之间。
4. 每条边都与 $x$ 轴或 $y$ 轴平行。
5. 每个内角为 $90$ 度或 $270$ 度。

请输出高桥构建护城河的不同方法数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are villages at some number of points in the $xy$-plane.
Takahashi will construct a moat to protect these villages from enemies such as civil armies and witches.

You are given a $4 \times 4$ matrix $A = (A_{i, j})$ consisting of $0$ and $1$.
For each pair of integers $(i, j)$ $(1 \leq i, j \leq 4)$ such that $A_{i, j} = 1$, there is a village at the coordinates $(i-0.5, j-0.5)$.

The moat will be a polygon in the plane. Takahashi will construct it so that the following conditions will be satisfied. (See also the annotation at Sample Input/Output 1.)

1. There is no self-intersection.
2. All villages are contained in the interior of the polygon.
3. The $x$- and $y$-coordinates of every vertex are integers between $0$ and $4$ (inclusive).
4. Every edge is parallel to the $x$- or $y$-axis.
5. Every inner angle is $90$ or $270$ degrees.

Print the number of ways in which Takahashi can construct the moat.

Constraints

• $A_{i, j} \in \lbrace 0, 1\rbrace$
• There is at least one pair $(i, j)$ such that $A_{i, j} = 1$.

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print the number of ways in which Takahashi can construct the moat.

Sample Input 1

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

Sample Output 1

1272

The two ways to construct the moat shown in the images below are valid.

The four ways to construct the moat shown in the images below are invalid.

Here are the reasons the above ways are invalid.

• The first way violates the condition: "There is no self-intersection."
• The second way violates the condition: "All villages are contained in the interior of the polygon."
• The third way violates the condition: "The $x$- and $y$-coordinates of every vertex are integers between $0$ and $4$." (Some vertices have non-integer coordinates.)
• The fourth way violates the condition: "Every edge is parallel to the $x$- or $y$-axis."

Sample Input 2

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

Sample Output 2

1

update @ 2024/3/10 09:41:56