사과를 더 많이 먹자

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 각 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸 중 하나이다. 격자의 위치는 $(r, c)$로 나타낸다. $r$은 행 번호, $c$는 열 번호이다. 행 번호는 맨 위가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽이 0이고 오른쪽으로 1씩 증가한다. 따라서 맨 왼쪽 위 칸은 $(0, 0)$, 맨 아래 오른쪽 칸은 $(4, 4)$이다.

두 학생이 보드의 서로 다른 칸에 있다. 첫 번째 학생은 $(r_1, c_1)$에, 두 번째 학생은 $(r_2, c_2)$에 있다. 학생은 한 번의 이동으로 상, 하, 좌, 우 중 한 방향으로 한 칸 이동할 수 있다. 사과가 있는 칸으로 이동하면 그 칸의 사과를 1개 먹는다. 장애물이 있는 칸으로는 이동할 수 없다. 학생이 지나간 칸은 학생이 그 칸을 떠나는 즉시 장애물이 있는 칸으로 바뀐다. 첫 번째 학생부터 두 학생이 번갈아 한 번씩 이동한다. 학생은 다른 학생이 있는 칸으로 이동할 수 없다. 자기 차례에 이동할 수 있는 칸이 없으면 차례가 상대방에게 넘어간다. 두 학생이 모두 이동할 수 없거나 보드의 사과를 모두 먹으면 게임이 끝난다.

두 학생은 자신이 먹는 사과 개수에서 상대 학생이 먹는 사과 개수를 뺀 값이 최대가 되도록 최적으로 행동한다. 게임이 끝났을 때 첫 번째 학생이 두 번째 학생보다 사과를 더 많이 먹었으면 1을, 그렇지 않으면 0을 출력한다.

첫 번째 줄부터 다섯 번째 줄까지 보드의 정보가 주어진다. $i$번째 줄의 $j$번째 숫자는 보드의 $(i-1)$행 $(j-1)$열 정보이다. 1은 사과가 1개 있는 격자, 0은 빈칸, -1은 장애물이 있는 격자이다.

다음 줄에 두 학생의 현재 위치 $r_1$, $c_1$, $r_2$, $c_2$가 빈칸을 사이에 두고 순서대로 주어진다.

최적으로 행동했을 때 게임이 끝난 후 첫 번째 학생이 두 번째 학생보다 사과를 더 많이 먹으면 1을, 그렇지 않으면 0을 출력한다.

• 두 학생의 현재 위치 $(r_1, c_1)$, $(r_2, c_2)$는 빈칸이다.
• $0 \le r_1, c_1, r_2, c_2 \le 4$
• $(r_1, c_1) \ne (r_2, c_2)$