Moat

题目描述

平面上在若干点处有村庄。
Takahashi 将构造一条护城河以保护这些村庄免受土匪和女巫等敌人的侵扰。 给定一个由 $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)$ 处有一个村庄。 护城河将在平面上为一个多边形。 Takahashi 将把它构造为满足以下条件。 （参见样例输入/输出 1 的注释。）

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

输出 Takahashi 可以构造护城河的方案数。

输入格式

标准输入的格式如下： $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 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

1272

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

1

提示

$A_{i, j} \in \lbrace 0, 1\rbrace$ 至少存在一对 $(i, j)$ 使得 $A_{i, j} = 1$。下面图片中展示的两种构造护城河的方式是 有效的。 下面图片中展示的四种构造护城河的方式是 无效的。 以下是上述无效方式的原因。

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

标签: AtCoder|abc219E

来源

AtCoder|abc219E