Connection Status:
Competition Arena > WallGameDiv2

WallGameDiv2

SRM 580 · 2012-12-13 · by snuke

SRM 580 · 2012-12-13 · by snuke · Dynamic Programming
Class Name: WallGameDiv2
Return Type: int
Method Name: play
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Rabbit and Eel are playing a board game. The game is played with a single token on a rectangular board that is divided into a grid of unit cells. Some cells contain a digit that represents the cost of placing the token onto that cell. Other cells contain the letter 'x' that represents a blocked cell. It is not allowed to place the token onto a blocked cell.

Initially, the token is placed on the leftmost cell of the topmost row. (The constraints guarantee that this cell will never be blocked and its cost will always be 0.) Eel starts the game by putting up some walls. Eel may place as many walls as he wants, including none. Each wall must be placed between two adjacent cells in the same column.

Once Eel has placed the walls, Rabbit gets to move the token. In each step, Rabbit may move the token one cell left, one cell right, or one cell down. (Note that Rabbit is not allowed to move the token upwards.) Rabbit may only move the token into cells that are not blocked. Each time Rabbit moves the token into a cell, he has to pay the cost associated with that cell.

The game ends when Rabbit first moves the token into the bottommost row. The constraints guarantee that this can be achieved if Eel does not place any walls. The game must always be allowed to end. That is, Eel must not place a set of walls that blocks all possible paths to the bottommost row.

Rabbit's goal is to minimize and Eel's goal is to maximize the total cost paid by Rabbit during the game. You are given the String[] costs representing the costs of cells: character j of element i of cost is either a digit that represents the cost written in the cell in row i, column j; or it is the letter 'x' that represents a blocked cell. Return the total cost of the game assuming that both Rabbit and Eel play optimally.

Constraints

  • costs will contain between 2 and 50 elements, inclusive.
  • Each element of costs will contain between 1 and 50 characters, inclusive.
  • Each element of costs will contain the same number of characters.
  • Each character of each element of costs will be a letter 'x' or a decimal digit ('0'-'9').
  • There will be at least one valid path from the leftmost cell of topmost row to a cell in the bottommost row.
  • costs[0][0] will always be '0'.
Examples
0)
{"042"
,"391"}
Returns: 13

Eel's optimal stategy is to put two walls: between '0'-'3' and between '2'-'1'. Then Rabbit's optimal strategy is to move the token along the path '0'->'4'->'9'. The total cost will be 13.

1)
{"0xxxx"
,"1x111"
,"1x1x1"
,"11191"
,"xxxx1"}
Returns: 16

There's only one path from the starting cell to the bottom row and Eel isn't allowed to block it. Rabbit will move the token along this path and will get to pay a cost of 16. Note that it is not allowed to move the token upwards.

2)
{"0"
,"5"}
Returns: 5
3)
{"01","0x"}
Returns: 0
4)
{"090","064","232"}
Returns: 22

Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WallGameDiv2 with a public method int play(vector<string> costs) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous