P2295 MICE

The zoo in country S is an $N \times M$ grid, with the top-left corner at $(1, 1)$ and the bottom-right corner at $(N, M)$. A little elephant is at the top-left corner and wants to go home to sleep at the bottom-right corner, but there are some mice in the zoo, and the elephant is afraid of them. The mice in the zoo are all distinct individuals. The elephant’s fear value is defined as the number of distinct mice it can see along its route home. If the elephant is currently at $(x_1, y_1)$, it can see a mouse if and only if the mouse at $(x_2, y_2)$ satisfies $|x_1 - x_2| + |y_1 - y_2| \leq 1$. Since the elephant is very sleepy, it will only take a shortest path home, i.e., it only moves down or right. Now you need to determine a route home that minimizes the elephant’s fear value.

The first line contains two integers, $N$ and $M$. Then an $N \times M$ matrix describes the map of the zoo. $A_{i, j}$ denotes the number of mice at row $i$, column $j$. If $A_{i, j} = 0$, it means there are no mice at that position (the elephant’s home may also contain mice).

Output a single integer, the minimal possible fear value over all routes.

For $20\%$ of the testdata, $1 \leq N, M \leq 5$. For $100\%$ of the testdata, $1 \leq N, M \leq 1000, 0 \leq A_{i, j} \leq 100$. Translated by ChatGPT 5