Connection Status:
Competition Arena > PathGame

PathGame

SRM 637 · 2014-08-25 · by snuke

SRM 637 · 2014-08-25 · by snuke · Dynamic Programming, Simple Math, Simple Search, Iteration
Class Name: PathGame
Return Type: String
Method Name: judge
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Cat Snuke and wolf Sothe are playing the Path Game.


The Path Game is played on a rectangular grid of square cells. The grid has 2 rows and some positive number of columns. Each cell is either black or white.


A left-to-right path in the grid is a sequence of white cells such that the first cell in the sequence is in the leftmost column, the last cell in the sequence is in the rightmost column, and each pair of consecutive cells shares a common side.


The initial coloring of the grid is such that there is at least one left-to-right path. You are given this initial coloring as a String[] board with two elements. For each i and j, board[i][j] is either '#' (representing a black cell) or '.' (representing a white cell).


The players take alternating turns. In each turn, the current player has to choose and color one white cell black. Snuke goes first. The game ends when there is no longer a left-to-right path on the board. The last player who colored a cell loses the game. In other words, the loser is the player who was forced to block the last left-to-right path.


Assume that both players play the game optimally. Return "Snuke" (quotes for clarity) if Snuke wins the game, and "Sothe" otherwise.

Constraints

  • board will contain 2 elements.
  • Each element in board will contain between 1 and 1000 characters, inclusive.
  • All elements in board will have the same length.
  • Each character in board will be '#' or '.'.
  • The grid described by board will contain a left-to-right path.
Examples
0)
{"#.."
,"..."}
Returns: "Snuke"

Snuke has exactly one winning move: he must color the lower right cell. After this move the resulting grid will still contain a left-to-right path. Sothe will then have four possible moves, but each of those loses the game immediately.

1)
{"#"
,"."}
Returns: "Sothe"

Snuke has to color the only white cell black, and he immediately loses the game.

2)
{"....."
,"..#.."}
Returns: "Sothe"
3)
{".#..."
,"....."}
Returns: "Snuke"
4)
{".....#..#........##......."
,"..........#..........#...."}
Returns: "Snuke"

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

Coding Area

Language: C++17 · define a public class PathGame with a public method string judge(vector<string> board) · 130 test cases · 2 s / 256 MB per case

Submitting as anonymous