34218번 - 숭고한 마법학교

숭고한 마법학교에서는 매년 8월 깊은 숲 속 대회장에서 마법 경진대회를 개최하고 있다! 2025년 숭고한 마법 경진대회의 운영진은 대회장에 도착하는 것도 대회의 일부라고 생각해, 참가자들에게 다음과 같이 공지했다.

숲의 지도가 제공되지만, 대회장까지 이동하는 경로가 있음을 보장하지 않습니다. 필요에 따라 텔레포트 마법을 이용해 대회장에 도착해야 합니다.

숲의 지도는 $N$행 $M$열의 2차원 격자 $A$로 주어진다. $1\leq r\leq N,1\leq c\leq M$을 만족하는 $r,c$에 대해, 격자 $A$의 $r$행 $c$열에는 $A_{r,c}$가 적혀 있으며, $r$행 $c$열을 편의상 $(r,c)$로 표현한다. $A_{r,c}$는 $0$ 또는 $1$이며, $1$인 경우는 지나갈 수 있는 칸을 의미하고 $0$인 경우 나무가 있어 지나갈 수 없는 칸을 의미한다. 나무가 없는 빈 공간으로는 상하좌우로 인접한 격자점으로만 이동할 수 있으며, 숲을 둘러싸는 결계가 있어 입구를 제외한 지점을 통해 숲으로 들어가거나 나갈 수 없다.

텔레포트 마법을 통해 $(r_1,c_1)$에서 $(r_2,c_2)$로 이동할 때 $\left\vert r_1-r_2 \right\vert +\left\vert c_1-c_2 \right\vert$ 만큼 마나를 사용한다. 텔레포트 마법은 재사용에 매우 오랜 시간이 걸려, 단 한 번만 사용할 수 있다.

대회에서 많은 마나를 사용할 예정이기에, 마나를 최소한으로 사용해 대회장에 도착해야 한다.

첫 줄에 격자의 크기 $N$, $M$이 주어진다. ($2\leq N,M\leq 1\, 000$)

이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $A_{i,1},A_{i,2},\ldots ,A_{i,M}$이 공백으로 구분되어 주어진다. ($0\leq A_{ij}\leq 1$)

다음 줄에 숲의 입구의 위치 $(s_r,s_c)$가 공백으로 구분되어 주어진다. ($1\leq s_r\leq N$; $1\leq s_c\leq M$)

마지막 줄에는 대회장의 위치 $(e_r,e_c)$가 공백으로 구분되어 주어진다. ($1\leq e_r\leq N$; $1\leq e_c\leq M$)

주어지는 숲의 입구와 대회장의 위치는 나무가 없어 지나갈 수 있는 칸임이 보장된다.

첫째 줄에 최소한의 마나를 사용하여 대회장에 도착할 때 사용하는 마나를 출력한다.