Chess Kings Chasing Game Solution Codechef september cook off 2021
There’s angrid where each cell of the grid contains a positive integer. Let be the positive integer on the cell positioned -th rows from the top and -th columns from the left.
Initially, Alice is at positionand Bob is at . Both players can move like a chess king on the grid: one step horizontally, vertically or diagonally. They can’t move out of the grid or stay in the same cell.
Alice starts with an initial score of. The game proceeds as follows:
- Alice moves to a neighboring cell of her choice (horizontally, vertically or diagonally). Her score increases by the integer on the cell she just moved to.
- If Alice and Bob are in the same cell, then the game ends, else Bob moves to a neighboring cell of his choice.
- If Alice and Bob are in the same cell, then the game ends, else go to step 1.
The goal of Alice is to maximize her score. The goal of Bob is to minimize Alice’s score. Both players play optimally. It can be proven that the game will end in a finite number of iterations.
You need to find the maximum score Alice can achieve.
Note: Over the course of the game, Alice can revisit cells multiple times. She gets the corresponding value added to her score each time she visits it.
- The first line contains an integer denoting the number of test cases. The test cases then follow.
- The first line of each test case contains four integers denoting the size of the grid, the row coordinate of Alice’s position, the column coordinate of Alice’s position, the row coordinate of Bob’s position, and the column coordinate of Bob’s position respectively.
- The next lines of each test case have integers each. The -th integer in the -th line denotes .
For each test case, output on one line the score Alice will have if both Alice and Bob play optimally.
- Sum of over all test cases does not exceed
Sample Input 1
3 2 1 1 2 2 1 10 5 6 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 10 4 1 3 1 4 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
Sample Output 1
10 30 8
For the first test case, Alice moves to positionand gets points. Bob then moves to and catches Alice. This is the optimal gameplay.
For the second test case, Alice moves toand gets points. Bob moves to . Then Alice moves to and gets another points. Bob them moves to . Finally, Alice moves to gaining a total of points. The game ends as Alice and Bob are in the same cell. This is a possible optimal gameplay.
For the third test case, the GIF below shows a possible optimal gameplay