25368번 - 사과를 더 많이 먹자

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

현재 두 명의 학생이 보드의 서로 다른 위치에 있다. 첫 번째 학생은 (r1, c1), 두 번째 학생은 (r2, c2) 위치에 있다. 두 명의 학생은 한 번의 이동으로 상, 하, 좌, 우 방향 중 한 가지 방향으로 한 칸 이동할 수 있다. 사과가 있는 칸으로 이동하면 해당 칸에 있는 사과를 1개 먹는다. 장애물이 있는 칸으로는 이동할 수 없다. 학생이 지나간 칸은 학생이 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경된다. 즉, 학생이 해당 칸에서 상, 하, 좌, 우 방향으로 한 칸 이동하는 즉시 해당 칸은 장애물이 있는 칸으로 변경된다. 첫 번째 학생부터 두 명의 학생이 교대로 이동하면서 사과를 먹는다. 두 명의 학생이 같은 칸으로 이동할 수 없다. 즉, 다른 학생이 있는 칸으로 이동할 수 없다. 학생이 본인 차례에 이동할 수 있는 칸이 없으면 다른 학생으로 이동 기회가 넘어간다. 두 명의 학생이 모두 이동할 수 없거나 보드에 있는 사과를 모두 먹으면 게임이 종료된다. 두 명의 학생은 상대방 보다 사과를 더 많이 먹도록 플레이를 한다. 즉, 내가 먹는 사과 개수에서 상대 학생이 먹는 사과 개수를 뺀 값이 최대가 되도록 플레이를 한다. 두 명의 학생이 최적의 플레이를 했을 때, 게임이 끝나고 나서 첫 번째 학생이 두 번째 학생보다 사과를 더 많이 먹으면 1, 그렇지 않으면 0을 출력한다.

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 정보가 주어진다. i번째 줄의 j번째 숫자는 보드의 (i - 1)번째 행 (j - 1)번째 열의 정보를 나타낸다. 보드의 정보가 1이면 해당 칸은 사과가 1개 있는 격자임을 나타내고, 0이면 빈칸이 있는 격자를 나타내고, -1이면 장애물이 있는 격자임을 나타낸다.

다음 줄에 두 학생의 현재 위치 r1, c1, r2, c2가 빈칸을 사이에 두고 순서대로 주어진다.

첫 번째 줄에 게임이 끝나고 나서 첫 번째 학생이 두 번째 학생보다 사과를 더 많이 먹으면 1, 그렇지 않으면 0을 출력한다.

• 두 학생의 현재 위치 (r1, c1), (r2, c2)는 빈칸이다.
• 0 ≤ r1, c1, r2, c2 ≤ 4
• (r1, c1) ≠ (r2, c2)