택시 거리

면접 대비

시간 제한1초메모리 제한256 MB

요약

0과 1로 이루어진 N×M 격자에 정확히 두 개의 1이 있을 때, 두 1 사이의 맨해튼 거리를 출력한다.

문제

택시 거리는 바둑판 모양의 도로망을 가진 도시에서 점 A에서 B까지의 최단 거리를 구할 때 도로를 따라서만 가는 가장 짧은 거리를 뜻한다.

위 사진에서 빨간색 선이 택시 거리이다. 점 A의 좌표가 $(x_1, y_1)$ 이고 점 B의 좌표가 $(x_2, y_2)$ 일 때, 두 점 사이의 택시 거리 $D$ 는 다음과 같다.

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

가로와 세로로 인접한 두 칸 사이의 거리를 1이라고 할 때, 두 개의 1 사이의 거리를 구하는 프로그램을 작성하시오.

첫 줄에 격자의 높이 $N$ 과 너비 $M$ 이 주어진다. $(2 \le N, M \le 1{,}000)$

두 번째 줄부터 $N$ 개의 줄에 걸쳐 $M$ 개의 숫자 0 또는 1이 예제 입력과 같이 공백으로 구분되어 주어진다.

1은 항상 두 개만 주어진다.

주어진 숫자들에서 1과 1 사이의 택시 거리를 출력한다.