P15567 [COCI 2025/2026 #5] Five Steps / Pet

The full score for this problem is $110$.

The frog Maša is playing in a lake consisting of $n$ rows and $m$ columns. Each cell of the lake is either the character $0$ (meaning water) or $1$ (meaning a lily pad). Maša can only stand on lily pads. From one lily pad, she can jump to any other lily pad in the same row or the same column. However, her jumps must alternate: if the previous jump changed the column, then the next jump must change the row. If the previous jump changed the row, then the next jump must change the column. Each time Maša jumps away from her current lily pad, that lily pad sinks and cannot be jumped onto again. Maša wants to visit a total of $5$ lily pads in one path (including the starting pad). She may choose any lily pad as the starting point. Compute how many paths satisfy the conditions. Two paths are considered different if the coordinates of the lily pads at any of positions $1 \sim 5$ are different.

The first line contains two natural numbers $n, m$ ($1 \le n, m \le 2000$). The next $n$ lines each contain $m$ characters ($0$ or $1$), describing the lake grid.

Output a single integer, the number of paths that satisfy the conditions.

#### Sample Explanation Explanation for Sample #1: The $4$ paths are: - $(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)$ #### Subtasks | Subtask | Score | Limit | | :-----: | :---: | :---: | | $1$ | $8$ | $n, m \le 4$ | | $2$ | $27$ | $n, m \le 10$ | | $3$ | $58$ | $n, m \le 400$ | | $4$ | $17$ | No additional constraints | Translated by ChatGPT 5