Taxicab Distance

Interview

Time limit1sMemory limit256 MB

Summary

Given an N by M grid of 0s and 1s with exactly two 1s, print the Manhattan distance between them.

Level: Easy2 of 10
Topics: Array, Implementation, Math, Brute force
Solved: No attempts yet

Problem

In a city whose roads form a grid, the taxicab distance between points A and B is the length of the shortest path from A to B that stays on the roads.

In the picture above, the red line is the taxicab distance. If point A has coordinates $(x_1, y_1)$ and point B has coordinates $(x_2, y_2)$ , the taxicab distance $D$ between the two points is

$D = |x_2 - x_1| + |y_2 - y_1|$

Assume the distance between two cells that share a horizontal or vertical side is 1. Write a program that finds the distance between the two 1s.

Input

The first line gives the height $N$ and the width $M$ of the grid. $(2 \le N, M \le 1{,}000)$

Starting from the second line, $N$ lines each contain $M$ digits, 0 or 1, separated by spaces as in the sample input.

There are always exactly two 1s.

Output

Print the taxicab distance between the two 1s in the given grid.

Examples1

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