Gomgomi's Diet Management 2

Time limit3.5sMemory limit1024 MB

Summary

Given a grid with obstacles, find the fewest new obstacles that cut every path from the top-left cell to the bottom-right cell.

Level: Medium6 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

Gomgomi walking toward the chicken

The grid has $N$ rows and $M$ columns, and a delicious chicken is placed at cell $(N,M)$ . Gomgomi starts at $(1,1)$ and wants to reach the chicken. Gomgomi can move up, down, left, and right freely, but cannot step onto a cell with an obstacle or leave the grid.

Chungchung blocking Gomgomi from reaching the chicken

Chungchung, Gomgomi's health trainer, decides to stop Gomgomi from reaching the chicken. Chungchung can place a new obstacle on any cell that currently has no obstacle to block the path. If some cells already have obstacles, Chungchung may be able to place fewer new ones.

Given the state of the grid, print the minimum number of additional obstacles Chungchung must place to block Gomgomi from reaching the chicken. Obstacles cannot be placed on $(1, 1)$ or $(N, M)$ .

Input

The first line contains integers $N$ and $M$ separated by a space. ( $1 \le N, M \le 2\ 000$ , $3 \le N \times M$ )

From the second line onward, the next $N$ lines give the state of the grid. $0$ means a cell that can be passed through, and $1$ means a cell with an obstacle that cannot be passed through.

It is guaranteed that $(1,1)$ and $(N,M)$ have no obstacles.

Output

Print the minimum number of additional obstacles Chungchung must place to block Gomgomi's movement.

Examples3

Example 1
Input
```
4 4
0 0 0 1
0 0 0 0
0 0 1 0
0 1 0 0
```
Expected output
```
1
```
Example 2
Input
```
3 3
0 1 1
1 1 1
1 1 0
```
Expected output
```
0
```

Example 3

Input

9 10
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 1 1 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0

Expected output