Balance
2015 TCO Parallel 2B · 2015-04-08 · by zxqfl
2015 TCO Parallel 2B · 2015-04-08 · by zxqfl · Math
Problem Statement
Problem Statement
There is an infinite grid of cells. Each cell is either black or white.
A component is a maximal 4-connected set of cells which are all the same color. (See the Notes for the definition of a 4-connected set.) Note that by this definition, each cell belongs to exactly one component.
The entire grid is currently white, except for one square region of cells in the grid.
You are given aString[] initial that specifies the current colors of cells in this region.
You want to change the colors of some cells in this region.
You are given aString[] target that specifies the desired colors of cells in this region.
Each character of initial and target represents a 10000 by 10000 square of cells, all of the same color.
If the squares of the region are numbered starting from (0, 0), then square (i, j) is initially white if and only if initial[i/10000][j/10000] (floored integer division) is the character '#'.
Black cells are represented by the character '.'.
The target state is specified in the same way.
Additionally, the configurations of cells described by initial and target have a special property:
There are no cells of the same color which share a corner but belong to different components.
For example, the following grid is not valid because the symbol # in the middle represents a square of 10000 times 10000 white cells, and the topmost rightmost of these cells shares its upper right corner with another white cell that is not in the same component.
You may change the grid in a sequence of moves.
In each move you may flip the color of any single cell.
Note that the flipped cell may even be located outside the region.
The move is only valid if the following conditions are all satisfied:
If it is possible to transform initial into target, return "Possible".
Otherwise, return "Impossible".
(All quotes are for clarity only.)
A component is a maximal 4-connected set of cells which are all the same color. (See the Notes for the definition of a 4-connected set.) Note that by this definition, each cell belongs to exactly one component.
The entire grid is currently white, except for one square region of cells in the grid.
You are given a
You want to change the colors of some cells in this region.
You are given a
Each character of initial and target represents a 10000 by 10000 square of cells, all of the same color.
If the squares of the region are numbered starting from (0, 0), then square (i, j) is initially white if and only if initial[i/10000][j/10000] (floored integer division) is the character '#'.
Black cells are represented by the character '.'.
The target state is specified in the same way.
Additionally, the configurations of cells described by initial and target have a special property:
There are no cells of the same color which share a corner but belong to different components.
For example, the following grid is not valid because the symbol # in the middle represents a square of 10000 times 10000 white cells, and the topmost rightmost of these cells shares its upper right corner with another white cell that is not in the same component.
##### #..## #.#.# #...# #####
You may change the grid in a sequence of moves.
In each move you may flip the color of any single cell.
Note that the flipped cell may even be located outside the region.
The move is only valid if the following conditions are all satisfied:
- The move does not change the number of white components.
- The move does not change the number of black components.
- The move does not violate the special property described above. (I.e., after the move, there must not be any cells of the same color which share a corner but belong to different components.)
If it is possible to transform initial into target, return "Possible".
Otherwise, return "Impossible".
(All quotes are for clarity only.)
Notes
- A 4-connected set of cells is a set of cells which satisfies this property: for any pair of cells in the set, there is a path connecting the cells in which (a) all cells in the path are in the set, and (b) adjacent cells in the path share a side (sharing only a corner is not enough).
Constraints
- N will be between 1 and 50, inclusive.
- initial and target will contain exactly N elements each.
- Each element of initial and target will have a length of exactly N.
- Each element of initial and target will be composed of the characters '#' and '.'.
- The grids described by initial and target satisfy the property that there are no cells of the same colour which share a corner but are part of different components.
Examples
0)
{"#"}
{"."}
Returns: "Impossible"
1)
{"..",
".."}
{".#",
"##"}
Returns: "Possible"
Do not forget that there are white cells everywhere around the region.
2)
{"...",
".#.",
"..."}
{"###",
"#.#",
"###"}
Returns: "Impossible"
3)
{".#.#.......",
"####.###...",
".....####..",
"..##.#.##.#",
".##..#.##.#",
".#######...",
".#....###.#",
".##.#.#....",
"..#...#...#",
"..#####...#",
"..........."}
{"...........",
".###....#..",
".#.#..#....",
".###.......",
".#####.....",
".#...#####.",
".#.#.....#.",
".#.#####.#.",
".#.......#.",
".#########.",
"..........."}
Returns: "Impossible"
4)
{".....",
".###.",
".....",
".###.",
"....."}
{".....",
".#.#.",
".#.#.",
".#.#.",
"....."}
Returns: "Possible"
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Balance with a public method string canTransform(vector<string> initial, vector<string> target) · 89 test cases · 2 s / 256 MB per case