Chess Kings Chasing Game Solution Codechef september cook off 2021

Chess Kings Chasing Game Solution Codechef september cook off 2021

There’s an N×NN×N grid where each cell of the grid contains a positive integer. Let Vi,jVi,j be the positive integer on the cell positioned ii-th rows from the top and jj-th columns from the left.

Initially, Alice is at position (Ax,Ay)(Ax,Ay) and Bob is at (Bx,By)(Bx,By). 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 00. The game proceeds as follows:

  1. 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.
  2. If Alice and Bob are in the same cell, then the game ends, else Bob moves to a neighboring cell of his choice.
  3. 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.

Input Format

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains four integers N,Ax,Ay,Bx,ByN,Ax,Ay,Bx,By 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 NN lines of each test case have NN integers each. The jj-th integer in the ii-th line denotes Vi,jVi,j.

Output Format

For each test case, output on one line the score Alice will have if both Alice and Bob play optimally.

Constraints

  • 1T601≤T≤60
  • 2N3002≤N≤300
  • 1Vi,j1091≤Vi,j≤109
  • 1Ax,Ay,Bx,ByN1≤Ax,Ay,Bx,By≤N
  • (Ax,Ay)(Bx,By)(Ax,Ay)≠(Bx,By)
  • Sum of NN over all test cases does not exceed 300300

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

Explanation

  • For the first test case, Alice moves to position (1,2)(1,2) and gets 1010 points. Bob then moves to (1,2)(1,2) and catches Alice. This is the optimal gameplay.

  • For the second test case, Alice moves to (3,3)(3,3) and gets 1010 points. Bob moves to (2,2)(2,2). Then Alice moves to (4,4)(4,4) and gets another 1010 points. Bob them moves to (3,3)(3,3). Finally, Alice moves to (3,3)(3,3) gaining a total of 3030 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

Chess Kings Chasing Game Solution Codechef september cook off 2021

Solution: Click here

Leave a Comment