34963번 - 열도 서브태스크

문제

바다 한가운데에 설곽 열도가 있다. 설곽 열도는 여러 개의 작은 섬들로 이루어져 있다. 각 섬은 상하좌우로 인접한 육지 칸들로 이루어진 하나의 연결 영역이고, 모든 바다는 연결되어 있다. 단, 바다는 육지와 달리 대각선으로 인접한 칸도 연결된 것으로 생각한다.

섬의 지도는 0ドル$과 1ドル$로만 이루어진 $[0,N+1]\times[0 , M+1]$ 격자 형태로 나타낼 수 있다. $i$번째 행, $j$번째 열에 위치한 칸을 $(i,j)$칸이라 할 때, 지도 상의 숫자 $A_{i,j}$에 대해 $A_{i,j}=1$은 $(i,j)$칸이 육지임을 의미하며, $A_{i,j}=0$은 $(i,j)$칸이 바다임을 의미한다. 이때, 육지 칸은 $[1,N]\times[1 , M]$ 범위에만 존재할 수 있다.

설곽 열도에는 버스가 운행하고 있는데, 버스를 통해 같은 행의 임의의 칸 또는 같은 열의 임의의 칸으로 이동할 수 있다. 이때 발생하는 비용은 이동 횟수당 1ドル$이다. 단, 육지 칸에서 출발하여 육지 칸으로만 이동할 수 있으며, 한 번의 이동을 할 때 시작 칸과 도착 칸 사이에 바다 칸이 한 개라도 있다면 이동할 수 없다. 즉, 시작 칸과 도착 칸을 잇는 직선 경로는 육지 칸으로만 이루어져 있어야 한다.

SSHS 여행사는 설곽 열도를 여행하려고 하는 관광객들을 위해, 설곽 열도의 임의의 두 육지 칸 사이를 버스를 타고 이동할 때 발생하는 비용의 최솟값을 계산해 주는 서비스를 제공하려고 한다. SSHS 여행사를 도와 $Q$개 상황의 비용을 계산해 주자.

입력

첫째 줄에 설곽 열도의 크기를 나타내는 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 설곽 열도의 지도가 주어진다. 그중 $i$번째 줄은 $A_{i,1},ドル $A_{i,2},ドル $\cdots,ドル $A_{i,M}$이 공백으로 구분되어 주어진다. $[1,N]\times[1 , M]$ 범위의 $A_{i,j}$만 주어짐에 유의하라.

$N+2$번째 줄에 수행해야 하는 쿼리의 개수 $Q$가 주어진다.

$N+3$번째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리의 내용이 x y z w의 형식으로 주어진다. 이 쿼리는 설곽 열도의 $(x,y)$ 칸에서 $(z,w)$ 칸으로 버스를 타고 이동할 때 발생하는 최소 비용을 구하는 쿼리이다.

출력

첫째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리의 정답을 차례대로 한 줄에 하나씩 출력한다.

만약 버스로 $(x,y)$칸과 $(z,w)$ 칸 사이를 이동할 수 없다면 대신 -1을 출력한다.

제한

• 1ドル\leq N\leq 1,円 000$.
• 1ドル\leq M\leq 1,円 000$.
• 0ドル\leq A_{i,j}\leq 1$ (1ドル\leq i\leq N,1\leq j\leq M$).
• $A_{i,0}=A_{i,M+1}=0$ (0ドル\leq i\leq N+1$)
• $A_{0,j}=A_{N+1,j}=0$ (0ドル\leq j\leq M+1$)
• 1ドル\leq Q\leq 100,円 000$.
• 1ドル\leq x_i\leq N$ (1ドル\leq i\leq Q$).
• 1ドル\leq y_i\leq M$ (1ドル\leq i\leq Q$).
• 1ドル\leq z_i\leq N$ (1ドル\leq i\leq Q$).
• 1ドル\leq w_i\leq M$ (1ドル\leq i\leq Q$).
• $A_{x_i,y_i}=1$ (1ドル\leq i\leq Q$).
• $A_{z_i,w_i}=1$ (1ドル\leq i\leq Q$).

서브태스크

노트