FoxAndGo3
SRM 594 · 2013-06-25 · by cgy4ever
SRM 594 · 2013-06-25 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
Fox Ciel is playing Go with Jiro.
Ciel plays black and Jiro plays white.
You are given a String[] board that represents a square board on which they play.
Black pieces are denoted 'x', white pieces 'o' and empty cells '.' (period).
In the current position no two white pieces are adjacent. Jiro has already given up and he will not be making any more moves. Ciel is considering making some more moves. Her goal now is to maximize the number of empty cells on the board.
In each move, Ciel can add a black piece onto an empty cell. After each move, all dead white pieces are removed from the board. A white piece is considered dead if its cell does not share a side with any empty cell.
Return the maximum number of empty cells on the board, after Ciel makes zero or more moves as described above.
In the current position no two white pieces are adjacent. Jiro has already given up and he will not be making any more moves. Ciel is considering making some more moves. Her goal now is to maximize the number of empty cells on the board.
In each move, Ciel can add a black piece onto an empty cell. After each move, all dead white pieces are removed from the board. A white piece is considered dead if its cell does not share a side with any empty cell.
Return the maximum number of empty cells on the board, after Ciel makes zero or more moves as described above.
Notes
- The rules described in the statement are not identical with the rules of Go. In particular, black pieces never die in this problem.
Constraints
- n will be between 3 and 50, inclusive.
- board will contain exactly n elements.
- Each element in board will contain exactly n characters.
- Each character in board will be one of 'o', 'x', and '.'.
- No two white pieces will be adjacent.
- Each white piece will be adjacent to at least one empty cell.
Examples
0)
{"o.o",
".o.",
"o.o"}
Returns: 5
The best solution is to put black pieces on (1,2), (2,1), (2,3), and then on (3,2). After that the board will look as follows: .x. x.x .x. There are 5 empty cells.
1)
{"...",
".o.",
"..."}
Returns: 8
This time the best solution is don't do any move.
2)
{"xxxxx",
"xxoxx",
"xo.ox",
"xxoxx",
"xxxxx"}
Returns: 4
3)
{".xox.",
".o.ox",
"x.o.o",
"ox.ox",
".ox.."}
Returns: 12
4)
{"o.o.o",
".ox..",
"oxxxo",
"..x..",
"o.o.o"}
Returns: 12
Submissions are judged against all 144 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndGo3 with a public method int maxEmptyCells(vector<string> board) · 144 test cases · 2 s / 256 MB per case