Vankin's Mile is a solitaire game played by young wizards on an n x n square...

    

Transcribed Image Text:

Vankin's Mile is a solitaire game played by young wizards on an n x n square grid. The wizard starts by placing a token on any square of the grid. Then on each turn, the wizard moves the token either one square to the right or one square down. The game ends when the wizard moves the token off the edge of the board. Each square of the grid has a numerical value, which could be positive, negative, or zero. The wizard starts with a score of zero; whenever the token lands on a square, the wizard adds its value to his score. The object of the game is to score as many points as possible, without resorting to magic. For example, given the grid below, the wizard can score 8-6 +7-3+4 = 10 points by placing the initial token on the 8 in the second row, and then moving down, down, right, down, down. (This is not the best possible score for these values.) -1 -4 5 -7 7 7-8 10 -5 -9 8 -6 0 -2 -6 -6 7 4 7 -3 -3 1 -6 4 -9 & (a) Give an algorithm (including pseudocode) to compute the maximum possible score for a game of Vankin's Mile, given the n x n array of values as input. (b) Prove that your algorithm is correct. (c) Analyze your algorithm's time and space requirements. Vankin's Mile is a solitaire game played by young wizards on an n x n square grid. The wizard starts by placing a token on any square of the grid. Then on each turn, the wizard moves the token either one square to the right or one square down. The game ends when the wizard moves the token off the edge of the board. Each square of the grid has a numerical value, which could be positive, negative, or zero. The wizard starts with a score of zero; whenever the token lands on a square, the wizard adds its value to his score. The object of the game is to score as many points as possible, without resorting to magic. For example, given the grid below, the wizard can score 8-6 +7-3+4 = 10 points by placing the initial token on the 8 in the second row, and then moving down, down, right, down, down. (This is not the best possible score for these values.) -1 -4 5 -7 7 7-8 10 -5 -9 8 -6 0 -2 -6 -6 7 4 7 -3 -3 1 -6 4 -9 & (a) Give an algorithm (including pseudocode) to compute the maximum possible score for a game of Vankin's Mile, given the n x n array of values as input. (b) Prove that your algorithm is correct. (c) Analyze your algorithm's time and space requirements.