Eat More Apples

A 5 x 5 board is given. The board is a grid of 1 x 1 square cells. Each cell is either an apple cell (one apple), an obstacle cell, or an empty cell. A cell is written as $(r, c)$, where $r$ is the row number and $c$ is the column number. Row numbers start at 0 at the top and increase by 1 going down. Column numbers start at 0 at the left and increase by 1 going right. So the top-left cell is $(0, 0)$ and the bottom-right cell is $(4, 4)$.

Two students are on the board at different cells. The first student is at $(r_1, c_1)$ and the second student is at $(r_2, c_2)$. In one move, a student can move one cell up, down, left, or right. If a student moves onto a cell with an apple, the student eats that apple. A student cannot move onto an obstacle cell. A cell that a student has moved through becomes an obstacle cell as soon as the student leaves it. The students take turns, starting with the first student, and each turn is one move. A student cannot move onto a cell occupied by the other student. If a student has no legal move on their turn, the turn passes to the other student. The game ends when neither student can move or when all apples on the board have been eaten.

Both students play optimally to maximize the number of apples they eat minus the number of apples the other student eats. After the game ends, print 1 if the first student eats more apples than the second student, and 0 otherwise.

The first line through the fifth line give the board. The number in row $i$ and column $j$ describes the cell at row $(i-1)$ and column $(j-1)$. A value of 1 means the cell has one apple, 0 means the cell is empty, and -1 means the cell is an obstacle.

The next line gives the current positions of the two students, $r_1$, $c_1$, $r_2$, and $c_2$, separated by spaces, in that order.

Print 1 if the first student eats more apples than the second student when the game ends under optimal play. Otherwise, print 0.

• The current positions $(r_1, c_1)$ and $(r_2, c_2)$ are empty cells.
• $0 \le r_1, c_1, r_2, c_2 \le 4$
• $(r_1, c_1) \ne (r_2, c_2)$