P15567 [COCI 2025/2026 #5] 五步 / Pet

本题满分 $110$。

青蛙 Maša 在一个由 $n$ 行 $m$ 列组成的湖里玩耍。湖的每个格子是字符 $0$（表示水）或 $1$（表示荷叶）。 Maša 只能站在荷叶上。她从一片荷叶可以跳到同一行或同一列的任意另一片荷叶。但她的跳跃方式必须交替：若上一次跳跃改变了列，那么下一次必须改变行。若上一次跳跃改变了行，那么下一次必须改变列。 每当 Maša 从当前荷叶跳走时，这片荷叶会下沉，之后不能再被跳到。 Maša 想在一条路径中访问总计 $5$ 片荷叶（包含起点）。她可以任选一片荷叶作为起点。请你计算一共有多少条满足条件的路径。若两条路径在第 $1\sim 5$ 个位置所处荷叶的坐标任意一个不同，则认为两条路径不同。

第一行包含两个自然数 $n,m$（$1 \le n,m \le 2000$）。 接下来 $n$ 行，每行包含 $m$ 个字符（$0$ 或 $1$），表示湖的矩阵。

输出一个一个整数，表示满足条件的路径条数。

#### 【样例解释】 样例 #1 解释： $4$ 条路径分别为： - $(1,1)\to(2,1)\to(2,2)\to(1,2)\to(1,3)$ - $(1,2)\to(2,2)\to(2,1)\to(1,1)\to(1,3)$ - $(1,3)\to(1,2)\to(2,2)\to(2,1)\to(1,1)$ - $(1,3)\to(1,1)\to(2,1)\to(2,2)\to(1,2)$ #### 【子任务】 | 子任务 | 分值 | 限制 | | :----: | :--: | :--: | | $1$ | $8$ | $n,m \le 4$ | | $2$ | $27$ | $n,m \le 10$ | | $3$ | $58$ | $n,m \le 400$ | | $4$ | $17$ | 无额外限制 |