102194: [AtCoder]ABC219 E - Moat

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

问题描述

在xy平面上的某个数的点上有村庄。
Takahashi将建造一个护城河来保护这些村庄免受民兵和女巫等敌人的侵害。

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

护城河将是平面上的一个多边形。 Takahashi将建造它，使以下条件得到满足。（参见示例输入/输出1的注释。）

1. 没有自相交。
2. 所有村庄都位于多边形的内部。
3. 每个顶点的x坐标和y坐标都在0和4之间（包括）。
4. 每条边都平行于x轴或y轴。
5. 每个内角为90度或270度。

打印Takahashi可以建造护城河的方法数。

约束

• $A_{i, j} \in \lbrace 0, 1\rbrace$
• 存在至少一对$(i, j)$，满足$A_{i, j} = 1$。

输入

输入以标准输入的以下格式给出：

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

输出

打印Takahashi可以建造护城河的方法数。

样例输入1

1 0 0 0

0 0 1 0

0 0 0 0

1 0 0 0

样例输出1

1272

下面两张图片中显示的建造护城河的两种方式是 有效 的。

下面四张图片中显示的建造护城河的四种方式是 无效 的。

以下是以上方式无效的原因。

• 第一种方式违反了条件：“没有自相交”。
• 第二种方式违反了条件：“所有村庄都位于多边形的内部”。
• 第三种方式违反了条件：“每个顶点的x坐标和y坐标都在0和4之间”。（有些顶点具有非整数坐标。）
• 第四种方式违反了条件：“每条边都平行于x轴或y轴”。

样例输入2

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出2

1