Road Reconstruction

Interview

Time limit1sMemory limit512 MB

Summary

Given a grid where cells cost 0, 1, or 2 to cross and -1 is blocked, find the minimum total construction cost of a path from the top-left to the bottom-right cell.

Level: Medium6 of 10
Topics: Graph, Shortest path, Heap, Matrix
Solved: No attempts yet

Problem

Flooding has destroyed the city's roads, causing inconvenience for many ICP (International Computational Plan) citizens. Suppose the city is represented as the grid below. A black cell denotes a 'unit road', and a white cell denotes a place where a road never existed or has been destroyed. A cell marked with X denotes a place where a road cannot be built.

Assuming cars in the city move along unit roads only horizontally or vertically, we want to compute the minimum road construction cost needed to create a path for the city's cars from the top-left cell to the bottom-right cell, restoring the city's function. Suppose that building one unit road costs 1 or 2. In the figure above, building one unit road on a white cell is assumed to cost 1.

Building the unit roads marked in gray as above costs 4, which achieves the goal.

Given the city as a grid like the above, write a program to find the minimum road construction cost needed to create a path from the top-left cell to the bottom-right cell.

Input

Input comes from standard input. The first line gives two positive integers m and n (1 ≤ m, n ≤ 1,000, 1 < m×n), the number of rows and columns of the grid representing the city. Each of the next m lines gives n numbers describing the cells of the grid. Each cell is given as an integer 0, 1, 2, or -1: 0 means a unit road already exists, that is, the road has not been destroyed; 1 means a cell with no unit road where a road can be built at cost 1; 2 means a cell with no unit road where a road can be built at cost 2; -1 means a cell marked X where a unit road cannot be built.

Output

Output goes to standard output. Print on one line the minimum road construction cost needed to create a path from the top-left cell of the city to the bottom-right cell. If such a path cannot be built, print -1.

Examples4

Example 1
Input
```
2 3
1 -1 -1
1 -1 2
```
Expected output
```
-1
```
Example 2
Input
```
2 3
-1 1 -1
1 1 -1
```
Expected output
```
-1
```

Example 3

Input

6 8
0 0 1 1 -1 1 0 1
1 0 1 1 1 1 1 1
1 0 0 -1 1 0 1 1
1 -1 1 1 1 0 1 1
1 0 1 0 0 0 1 1
1 0 0 0 1 1 1 0

Expected output

Example 4

Input

6 8
2 0 1 1 -1 1 0 1
1 0 1 1 1 1 1 1
1 0 0 -1 1 0 1 1
1 -1 2 1 1 0 1 1
1 0 2 0 0 0 -1 1
1 0 0 0 1 2 2 0

Expected output