该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

输入 #1

2 3
111
110

输出 #1

4

输入输出样例 #2

输入 #2

4 4
1111
1111
1111
1111

输出 #2

2304

输入输出样例 #3

输入 #3

2 5
11110
01111

输出 #3

48

说明/提示

【样例解释】

样例 #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)$

【子任务】