E - 护城河

得分：500 点

问题描述

平面上有一些点表示村庄。
高桥将修建护城河来保护这些村庄，以免被敌人攻击，例如区分军队和女巫。

给你一个 $4 \times 4$ 矩阵 $A = (A_{i, j})$，由 $0$ 和 $1$ 组成。
对于每对整数 $(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$ 度。

输出高桥构建护城河的方式数量。

约束

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

输出

输出高桥构建护城河的方式数量。

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

1272

如下图所示，有两个有效的构建方式。

如下图所示，有四个无效的构建方式。

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

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

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

1