Connection Status:
Competition Arena > BoardEscapeDiv2

BoardEscapeDiv2

SRM 676 · 2015-11-03 · by lg5293

SRM 676 · 2015-11-03 · by lg5293 · Dynamic Programming
Class Name: BoardEscapeDiv2
Return Type: String
Method Name: findWinner
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Alice and Bob have a rectangular board divided into a grid with r rows and c columns. The grid is described by the String[] s. Each character of s represents one cell. There are four types of cells:

  • 'E' denotes an exit. There may be arbitrarily many exits, possibly zero.
  • 'T' means the square contains a single token. Initially there will be exactly one token on the entire board.
  • '#' denotes an obstacle.
  • '.' denotes an empty cell.

Alice and Bob will play a game on this board. The game is parameterized by the int k. The token initially has the number k on it. The players will take alternating turns, starting with Alice. A player's turn consists of the following steps:

  1. The player moves the token one square up, down, left, or right. The token cannot go over the edge of the board and it cannot enter a cell with an obstacle.
  2. If this token is on an exit, it disappears from the board.
  3. Otherwise, subtract one from the number on the token. If the number on the token is zero, remove it from the board.

The first player unable to make a move loses the game. (This happens when the token is stuck and also when it already left the board.)

You are given the String[] s and the int k Compute the winner of the game, assuming both Alice and Bob play optimally. Return the winner's name: either "Alice" or "Bob". Note that the return value is case-sensitive.

Constraints

  • r,c will be between 1 and 50, inclusive.
  • s will contain exactly r elements, each consisting of c characters.
  • Each character of each element of s will be one of 'T', 'E', '#', or '.'.
  • There will be exactly 1 'T' charcters within all elements of s.
  • k will be between 1 and 100, inclusive.
Examples
0)
{"T.#",
 "#.E"}
3
Returns: "Alice"

The token starts in row 0, column 0. At the beginning of the game the number on the token is 3. In her first move Alice must push the token to the right and decrease the number to 2. Bob can then move the token either left (back where it started) or down. Either way, after Bob's move the number on the token will be 1. Regardless of which option Bob chose, Alice can always make the token disappear in her second move: either she reaches the exit, or the token disappears on its own after its counter reaches zero. Afterwards Bob cannot make his second move and therefore Alice wins the game.

1)
{"E#E",
 "#T#",
 "E#E"}
99
Returns: "Bob"

As the token is stuck between obstacles, Alice has no valid move to make and therefore she immediately loses the game.

2)
{"#E...",
 "#...E",
 "E.T#.",
 "..#.."}
13
Returns: "Alice"
3)
{"TE"}
50
Returns: "Alice"
4)
{".T."}
1
Returns: "Alice"

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

Coding Area

Language: C++17 · define a public class BoardEscapeDiv2 with a public method string findWinner(vector<string> s, int k) · 123 test cases · 2 s / 256 MB per case

Submitting as anonymous