TopCoder SRM 580 - 1000: WallGameDiv1

Problem Statement

Rabbit 和 Eel 在玩一个游戏.
游戏在一个 n * m 的棋盘上进行,
在这个游戏中, 玩家需要操作一个棋子, 将它从第一行移动到最后一行(当棋子被移动到最后一行时, 游戏立刻结束).
在第 i 行第 j 列有一个数字 a[i][j], 表示经过这个格子的代价.

游戏由若干轮组成. 每一轮由 Rabbit 先操作. 在第一轮, Rabbit 会把一个棋子放在第一行的某一列上, 并付出相应的费用.
在接下来的每一轮中, Rabbit 先把棋子向左, 向右, 或向下移动一步, 然后付出相应的费用.
然后由 Eel 操作. Eel 可以选取一对 (i, j), 其中 1 <= i < n 并且 1 <= j < m, 然后在 (i, j) 和 (i + 1, j) 之间修建一堵墙.
Eel 每次操作可以修建任意多的墙, 但是在任意时刻, Eel 修建的墙都不能够使游戏无法结束
(也就是说, Eel 修建的墙不能阻止棋子从当前的位置移动到最后一行).

Rabbit 的目标是最小化花费, 而 Eel 的目标是最大化 Rabbit 的花费. 现在假设双方都绝顶聪明, 你需要求出最后的花费.

注意: 多次经过同一个位置的花费算多次 .

1 <= n, m <= 50, 0 <= a[i][j] <= 9.

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. Each cell contains a digit that represents the cost of placing the token onto that cell.

The game is played in turns. In each turn, Rabbit moves first and Eel moves second. In the first turn, Rabbit places the token onto one of the cells in the topmost row, and he pays the associated cost. In each of the following turns, Rabbit moves the token one cell left, right, or down, and pays the cost written in the target cell. (Note that Rabbit is not allowed to move the token upwards.) Eel never moves the token. Instead, in each turn, Eel gets to place some walls. In each turn, Eel may place as many walls as he wants, including none. Each wall must be placed between two adjacent cells in the same column.

The game ends when Rabbit first moves the token into the bottommost row. The game must always be allowed to end. That is, Eel must never place a wall that would prevent Rabbit from reaching the bottommost row from the token's current location. 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 represents the cost written in the cell in row i, column j. Return the total cost of the game assuming that both Rabbit and Eel play optimally.

Definition

Class WallGameDiv1
Method play
Parameters vector<string>
Returns int
Method signature int play(vector<string> costs)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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 between '0' and '9', inclusive.

Test cases

input
- costs {"12",
  "34"}
output
Returns 6
note
One possible gameplay is as follows:
- Rabbit puts a token on '2' and pays 2.
- Eel puts a wall between '2' and '4'
- Rabbit moves the token to '1' and pays 1.
- Eel does nothing.
- Rabbit moves the token to '3', pays 3, and the game ends.
The total cost is 2+1+3 = 6.
input
- costs {"99999",
  "99999",
  "99999"}
output
Returns 99
note
Let's label the cells in the following way:
```
ABCDE
FGHIJ
KLMNO
```
We will not show you the optimal strategy. Instead, we will just show you one possible gameplay.
- Rabbit puts a token on C and pays 9.
- Eel puts eight walls: between AF, BG, CH, DI, GL, HM, IN, and JO.
- Rabbit moves the token to D and pays 9.
- Eel does nothing.
- Rabbit moves the token to E and pays 9.
- Eel does nothing.
- During next several turns, Rabbit will move the token along the path E->J->I->H->G->F and Eel does nothing.
- Rabbit moves the token to K, pays 9, and ends the game with total cost 81.
In the above example, neither player played optimally.
input
- costs {"11111",
  "90005"}
output
Returns 10
note
Let's label the cells in the following way:
```
ABCDE
FGHIJ
```
Again, we will not show you the optimal strategy. Instead, we will just show you one possible gameplay.
- Rabbit puts a token on C.
- Eel puts three walls: between BG, CH, and DI.
- Rabbit moves the token to D and pays 1.
- Eel puts a wall between EJ.
- Now Rabbit is forced to move the token back. Rabbit will move the token along the path D->C->B->A->F and Eel does nothing.
- The game ends with total cost 14.
input
- costs {"4417231387449337370319219832088987579792",
  "3117295688208899006196193430472892512797",
  "0835796222361526836944954410684516919758",
  "1988200069973565052900745230547016216225",
  "8080511471118865780390486996601082102418",
  "4229084185957675819725844582167613108400",
  "9068653877952162764545674979144308771754",
  "8551565425951612499712254182109991511690",
  "7090525592007482152807163656647658543093",
  "9198968742256995592729889137556032960142",
  "2071864379877766468141740053503050313101",
  "1055375249261868472993219156394129253481",
  "2461178270502857106406495509025426298874",
  "8216781259733537757203421037984512664825",
  "4693452554407216935375049784445568498482",
  "2709693439640250842244170297203200674391",
  "5122217695676372684217182241705137947908",
  "6668814191410691246849638388008228444294",
  "4952122070212780440963814752538149378639",
  "9827737761436134120332969866554332504400",
  "3412406588339828249986707470540386748886",
  "7521506848088506994554600408372456405830",
  "1916926179183007872881163173153907665999",
  "6636166791472761992310264951474925339024",
  "6679667717747231380196787943691121008076",
  "3218993234115685151069259138068533004433",
  "4920152552986426962081492913852060211795",
  "0365186235986445521382132973036266396894",
  "3205351414936828189305188614651974318855",
  "3144278971529524658788277656125598825426",
  "5525287537572356662391582052968411726245",
  "2130137226726919525622574701068062252930",
  "2369996694245544770519574837226971226841",
  "6806769058165410189286521891570936341547",
  "0448109211631660241710734664066810078242",
  "4622919135804954122810530631429501069659",
  "0235247446548732490429856705369583140671",
  "2193399741215975228987754171460722199304",
  "1203037020703833716225328076959743850915",
  "5419885193880826109484912489603262199432"}
output
Returns 7366

back to the menu

SRM 580 1 1000 WallGameDiv1

Problem Statement

Definition

Limits

Constraints

Test cases