PathGameDiv2
SRM 637 · 2014-08-25 · by snuke
Problem Statement
Cat Snuke is 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
Snuke may color some of the white cells black. After he does so, there must still be at least one left-to-right path left on the board. The goal of the game is to color as many cells black as possible. Compute and return the largest number of cells Snuke can color black. (Note that the cells that are already black do not count.)
Constraints
- board will contain 2 elements.
- Each element in board will contain between 1 and 50 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.
{"#...."
,"...#."}
Returns: 2
Snuke can color at most two white cells black. One possible final state of the board looks as follows: #.... ..###
{"#"
,"."}
Returns: 0
Snuke can't color any cells.
{"."
,"."}
Returns: 1
{"....#.##.....#..........."
,"..#......#.......#..#...."}
Returns: 13
{"."
,"#"}
Returns: 0
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PathGameDiv2 with a public method int calc(vector<string> board) · 115 test cases · 2 s / 256 MB per case