| E - Bishop's Walk |
You need to find the best strategy to win a game. In this game, a board is divided into squares arranged in a square grid (like a chessboard, but the number of squares may be different from 64). Each square has a number between 0 and 9 in it, which indicates its value.
A chess bishop starts in a given square and you have to move it a number of times (l) diagonally (as in chess, it should move the same distance vertically and horizontally). Each time, you win the number of points of the destination square.
For example, for the following board:
Starting at the circled square and with 4 moves, the blue path earns 17 points. On the other hand, the green path obtains 36 points, which is the maximum in this case.
The program will receive the size of the board, the number of moves (l), and the coordinates of the starting square. It should calculate the maximum number of points that can be won from the starting square in l moves.
The input format is as follows:
An integer in a single line which says the number of problems to solve. Then, for each problem:
Two integers in a line separated by a space indicating the width of the board (n) and the number of moves (l). The height of the board is always the same as its width.
Two integers in a line separated by a space indicating the horizontal and vertical coordinates, respectively, of the starting square. Coordinates start at 0 at the top left corner and increase rightwards and downwards.
n rows of n numbers each indicating the value of each square.
Both n and l are less or equal than 50.
For each problem, a line with a single number indicating the maximum amount of points that can be obtained doing l moves starting from the given square.
1
8 4
6 5
1 0 3 7 2 5 4 6
3 5 9 9 6 7 1 6
0 1 1 8 1 4 1 1
9 2 5 8 6 2 6 5
4 9 2 7 5 7 4 8
2 3 8 9 0 9 5 0
1 6 8 3 0 0 4 0
2 9 9 8 2 5 3 7
36