← 返回题目列表

AtCoder · abc219_e

H. 护城河

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

区域内的一些地点有村庄 xy- 平面。
高桥将建造一条护城河来保护这些村庄免受民间军队和女巫等敌人的侵害。

您将获得 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 or 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

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