18128번 - 치삼이의 징검다리 건너기

치삼이는 가로로 N, 세로로 N만큼의 정사각형 모양 계곡을 지나가려고 한다. 하지만 엄청난 더위로 인해 물이 모두 말라버렸다!

계곡은 땅과 돌로 이루어져 있다. 전체 땅은 1×1크기의 땅들로 이루어져있고 땅에 돌이 존재할 수 있다. 그런데 계곡의 땅과 돌이 너무 뜨거워서 지나갈 수가 없다. 하지만 돌이 있는 부분은 물이 차오르면 식어서 지나갈 수 있게 된다. 다행히 마음씨 좋은 학생들이 치삼이를 위해 땅을 파서 물이 생성되는 곳을 만들어냈고 치삼이는 돌을 밟고 계곡을 지나가기로 했다. 물 생성지에는 땅이나 돌 모두 존재할 수 있다. 물은 물이 존재하는 위치에서 하루에 한 번 물과 인접한 곳으로 퍼진다. 이때, 대각선은 인접해 있다고 보지 않는다.

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

첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1,000), 물 생성지 개수 W(1 ≤ W ≤ N)가 주어진다.

두 번째 줄부터 W+1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x, y ≤ N)가 주어진다.

W+2줄부터 N개의 줄에 냇가의 지도가 주어진다. 1은 돌이 있는 위치를 나타내고, 0은 땅이 있는 위치를 나타낸다.

N, W, x, y는 모두 양의 정수이다.

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