Vankins Mile is a solitaire game played on an n X n square grid. The player starts by placing a token on any square of the grid. Then on each turn, the player moves the token either one square to the right or one square down. The game ends when…
Vankin’s Mile is an American solitaire game played on an n ? n square grid. The
player starts by placing a token on any square of the grid. Then on each turn, the player moves
the token either one square to the right or one square down. The game ends when player moves
the token o the edge of the board. Each square of the grid has a numerical value, which could be
positive, negative, or zero. The player starts with a score of zero; whenever the token lands on a
square, the player adds its value to his score. The object of the game is to score as many points
as possible. For example, given the grid below, the player can score 8 − 6 + 7 − 3 + 4 = 10 points
by placing the initial token on the in the second row, and then moving down, down, right, down,
down. (This is not the best possible score for this grid of numbers.)
(a) Describe and analyze an ecient algorithm to compute the maximum possible score for a game
of Vankin’s Mile, given the n × n array of values as input.
(b) In the European version of this game, appropriately called Vankin?s Kilometer, the player
can move the token either one square down, one square right, or one square left in each turn.
However, to prevent infinite scores, the token cannot land on the same square more than
once. Describe and analyze an ecient algorithm to compute the maximum possible score for
a game of Vankin’s Kilometer, given the n × n array of values as input.
Vankin’s Mile is an American solitaire game played on an n ? n square grid. The
player starts by placing a token on any square of the grid. Then on each turn, the player moves
the token either one square to the right or one square down. The game ends when player moves
the token o the edge of the board. Each square of the grid has a numerical value, which could be
positive, negative, or zero. The player starts with a score of zero; whenever the token lands on a
square, the player adds its value to his score. The object of the game is to score as many points
as possible. For example, given the grid below, the player can score 8 − 6 + 7 − 3 + 4 = 10 points
by placing the initial token on the in the second row, and then moving down, down, right, down,
down. (This is not the best possible score for this grid of numbers.)
(a) Describe and analyze an ecient algorithm to compute the maximum possible score for a game
of Vankin’s Mile, given the n × n array of values as input.
(b) In the European version of this game, appropriately called Vankin?s Kilometer, the player
can move the token either one square down, one square right, or one square left in each turn.
However, to prevent infinite scores, the token cannot land on the same square more than
once. Describe and analyze an ecient algorithm to compute the maximum possible score for
a game of Vankin’s Kilometer, given the n × n array of values as input.