시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 300 MB 70 21 14 26.923%

문제

치삼이는 가로로 N, 세로로 N만큼의 직사각형 모양 계곡을 지나가려고 한다. 하지만 엄청난 더위로 인해 물이 모두 말라버렸다! 계곡은 땅과 돌로 이루어져 있는데 땅과 돌이 너무 뜨거워서 지나갈 수가 없다. 하지만 돌이 있는 부분은 물이 차오르면 식혀져서 지나갈 수 있게 된다. 다행히 마음씨 좋은 학생들이 치삼이를 위해 땅을 파서 물이 생성되는 곳을 만들어냈고 치삼이는 돌을 밟고 계곡을 지나가기로 했다. 물 생성지 W에는 땅이나 돌 모두 존재할 수 있다. 물은 물이 존재하는 위치에서 하루에 한번 물과 인접한 곳으로 퍼진다. 이 때, 대각선은 인접해 있다고 보지 않는다.

치삼이는 현재 시작지점(1, 1)에서 도착지점(N, N)까지 가려고 한다. 시작지점(1, 1)과 도착지점(N, N)의 위치에는 항상 돌이 존재하며 물과 만나지 않아도 치삼이가 이동할 수 있다. 치삼이가 이동하는 것에는 시간이 걸리지 않는다. 치삼이는 상,하,좌,우,대각선으로 이동할 수 있다. 이때 치삼이가 도착지점(N, N)의 위치까지 가장 빠르게 도착하는 경우 몇일이 걸리는지 알아보자.

입력

첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1000), 물 생성지 개수 W(1 ≤ WN-2)가 주어지고 그 다음 줄부터 W + 1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x , yN)가 주어진다. 그 다음 줄부터 N줄까지 냇가의 지도가 주어진다. (1은 돌이 있는 위치를 나타내고, 0은 땅이 있는 위치를 나타낸다.)

출력

가장 빠르게 도착지점에 도착하는 일 수를 출력한다. 만약 치삼이가 도착지점(N, N)에 도달하지 못하는 경우 -1을 출력한다.

예제 입력 1

3 1
1 1
101
101
011

예제 출력 1

3

다음 그림과 같이 물이 퍼져, 물이 닿은 돌은 치삼이가 이동할 수 있다. 

예제 입력 2

6 3
5 4
1 6
6 4
110111
110011
011000
001010
111101
111001

예제 출력 2

5