E - Moat Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

xy -平面上のいくつかの点に村があります。
高橋君はこれらの村を民兵や魔女などの外敵から守るため、これらのすべての村を囲むようなお堀を建設します。

0 と 1 からなる 4 \times 4 行列 A = (A_{i, j}) が与えられます。
A_{i, j} = 1 を満たす整数の組 (i, j) (1 \leq i, j \leq 4) ごとに、座標 (i-0.5, j-0.5) に村があります。

お堀は平面上の多角形です。 高橋君は以下の条件をすべて満たすお堀を建設します（入力例１・出力例１の説明も参考にして下さい）。

  1. 自己交差がない
  2. 内部にすべての村を含む
  3. すべての頂点の x 座標と y 座標は 0 以上 4 以下の整数
  4. すべての辺は x 軸と y 軸のどちらかに平行
  5. それぞれの内角の大きさは 90 度または 270 度

高橋君が建設するお堀として考えられるものが何通りあるかを出力して下さい。

制約

  • A_{i, j} \in \lbrace 0, 1\rbrace
  • A_{i, j} = 1 となる (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

下記の 2 つの画像の例は、高橋君が建設するお堀の条件を満たします。

下記の 4 つの画像の例は、高橋君が建設するお堀の条件を満たしません。

上記の 4 つの例が高橋君の建設するお堀の条件を満たさない理由は、以下の通りです。

  • 1 つ目の画像の例は、「自己交差がない」という条件を満たしません。
  • 2 つ目の画像の例は、「内部にすべての村を含む」という条件を満たしません。
  • 3 つ目の画像の例は、「すべての頂点の x 座標と y 座標は 0 以上 4 以下の整数」という条件を満たしません。（座標が整数でない頂点があります。）
  • 4 つ目の画像の例は、「すべての辺は x 軸と y 軸のどちらかに平行」という条件を満たしません。

入力例 2

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

出力例 2

1

Score : 500 points

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