{"problem":{"name":"Moat","description":{"content":"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$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc219_e"},"statements":[{"statement_type":"Markdown","content":"There are villages at some number of points in the $xy$\\-plane.  \nTakahashi will construct a moat to protect these villages from enemies such as civil armies and witches.\nYou are given a $4 \\times 4$ matrix $A = (A_{i, j})$ consisting of $0$ and $1$.  \nFor 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)$.\nThe 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.)\n\n1.  There is no self-intersection.\n2.  All villages are contained in the interior of the polygon.\n3.  The $x$\\- and $y$\\-coordinates of every vertex are integers between $0$ and $4$ (inclusive).\n4.  Every edge is parallel to the $x$\\- or $y$\\-axis.\n5.  Every inner angle is $90$ or $270$ degrees.\n\nPrint the number of ways in which Takahashi can construct the moat.\n\n## Constraints\n\n*   $A_{i, j} \\in \\lbrace 0, 1\\rbrace$\n*   There is at least one pair $(i, j)$ such that $A_{i, j} = 1$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ $A_{1, 4}$\n$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ $A_{2, 4}$\n$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ $A_{3, 4}$\n$A_{4, 1}$ $A_{4, 2}$ $A_{4, 3}$ $A_{4, 4}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc219_e","tags":[],"sample_group":[["1 0 0 0\n0 0 1 0\n0 0 0 0\n1 0 0 0","1272\n\nThe two ways to construct the moat shown in the images below are **valid**.\n![image](https://img.atcoder.jp/ghi/7b3181deb4e1df72e4c0661b1137db4d.png) ![image](https://img.atcoder.jp/ghi/a1e46c7db32d63942caa7119a4f3a593.png)\nThe four ways to construct the moat shown in the images below are **invalid**.\n![image](https://img.atcoder.jp/ghi/335053c01a13eb99e55767a3dc02eb38.png) ![image](https://img.atcoder.jp/ghi/c4df3d1fa24557b0d4d94ac0eaa8b9ab.png) ![image](https://img.atcoder.jp/ghi/be93de595e9222d5e20c90bd28d24563.png) ![image](https://img.atcoder.jp/ghi/37dac3af065c013ce0b8c0ee7591b97a.png)\nHere are the reasons the above ways are invalid.\n\n*   The first way violates the condition: \"There is no self-intersection.\"\n*   The second way violates the condition: \"All villages are contained in the interior of the polygon.\"\n*   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.)\n*   The fourth way violates the condition: \"Every edge is parallel to the $x$\\- or $y$\\-axis.\""],["1 1 1 1\n1 1 1 1\n1 1 1 1\n1 1 1 1","1"]],"created_at":"2026-03-03 11:01:14"}}