22255번 - 호석사우루스

음머... 미련한 소인 호석사우루스는 융통성 따위 일절 가지지 않는다. 자신의 철칙에 맞게 우직하게 미궁을 탈출하려고 한다. 미궁은 $N$행 $M$열의 격자로 이루어져 있고 각 칸마다 입장하는 순간 받는 충격량이 있다. 같은 방을 여러 번 들어가면, 들어갈 때마다 같은 충격량을 받게 된다. 당연히 똑똑한 소라면 최소의 충격을 받으면서 미궁을 탈출하던가, 애초에 미궁에 안 빠지도록 머리를 썼겠지만, 호석사우루스는 그런 거 없다!

그의 철칙은, 이동 방식에 있다. 매 이동 시 마다 움직일 수 있는 방향이 다르다.

• $3K$ 번째 이동 시에는 상, 하, 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
• $3K+1$ 번째 이동 시에는 상, 하로 인접한 곳 중 한 칸으로 이동할 수 있다.
• $3K+2$ 번째 이동 시에는 좌, 우로 인접한 곳 중 한 칸으로 이동할 수 있다.
• 만약 이동하려는 곳에 벽이 있으면 이동할 수 없다.
• 최초의 이동은 1번째 이동이고, 이후에 2번째, 3번째 이동이다.

자신의 철칙을 지키되, 아픈 건 싫어하는 호석사우루스를 도와서 탈출구까지의 최소 충격량을 구해주자!

첫 번째 줄에 격자의 크기 $N$, $M$이 주어진다.

두 번째 줄에 시작 지점과 도착 지점의 정보인 $S_x$, $S_y$, $E_x$, $E_y$ 가 공백으로 구분되어 주어진다. 시작 지점이 $S_x$행 $S_y$열이며 도착 지점이 $E_x$행 $E_y$열임을 의미한다. 시작 지점과 도착 지점은 항상 다르다.

세 번째 줄부터 $N$ 개 줄에 걸쳐서 지도의 정보가 주어진다. 각 줄마다 $M$ 개의 정수가 주어진다. $i+2$번 줄의 $j$번째 숫자는 $i$행 $j$열에 위치한 격자의 충격량을 의미한다. 만약 충격량 정보가 $-1$이라면 해당 격자는 벽임을 의미한다.

시작점과 도착점의 충격량은 0 임이 보장된다.

첫 번째 줄에 호석사우루스가 탈출하는 과정에서 받는 최소 충격량을 출력한다. 만약 탈출하지 못한다면 $-1$ 을 출력한다.

• 1 ≤ $N$, $M$ ≤ 100
• 1 ≤ $S_x, E_x$ ≤ $N$
• 1 ≤ $S_y, E_y$ ≤ $M$
• -1 ≤ 각 칸의 충격량 ≤ 300