BlockTheBlockPuzzle
SRM 625 · 2013-12-22 · by vexorian
SRM 625 · 2013-12-22 · by vexorian · Graph Theory, Search
Problem Statement
Problem Statement
Block Puzzle is played on a square grid of unit cells. Some of those cells are marked as start cells, and one is marked as a goal cell.
The player begins by placing a 1x1x2 block on top of one of the start cells in such a way that the 1x1 face of the block coincides with the cell. The goal of the game is to reach the state where the block stands with its 1x1 face covering the goal cell. The game is played by rolling the block across the board. Only some types of moves are allowed: When the block stands on its 1x1 face, the player may roll the block in either of the four basic directions. However, when the block's bottom face is 2x1, the player may only roll it onto one of its 1x1 faces. In other words, the block must always be rolled over an edge of length 1.
All allowed moves are shown in the figure below. (The old state of the block is always semi-transparent, the new state is opaque.)
So far, the game seems trivial. Its difficulty comes from the fact that there are holes instead of some cells. Whenever the entire bottom face of the block stands on a hole, the block falls through the hole and the player loses the game. The block also falls off if the player rolls it across the edge of the game board. (Note that if the block stands on a 2x1 face and only one of the two cells under the face is missing, the block is still safe. Technically, the block would also be safe with one half of its bottom face sticking out of the game board, but obviously a move into such a configuration will never help you reach the goal.)
Bohn has been playing Block Puzzle too much. Jrus is bored, so he decided to make Bohn's game unsolvable by making more holes into his board. Jrus can only remove cells that are neither starting nor goal. As he doesn't want to get caught, he wants to remove as few cells as possible.
You are given the current board as aString[] board.
The character '.' represents an ordinary cell, 'H' is a hole, 'b' is a starting cell, and '$' is the only goal cell.
Return the smallest number of cells that have to be removed in order to make the puzzle unsolvable.
If it is not possible to make the puzzle unsolvable, return -1 instead.
The player begins by placing a 1x1x2 block on top of one of the start cells in such a way that the 1x1 face of the block coincides with the cell. The goal of the game is to reach the state where the block stands with its 1x1 face covering the goal cell. The game is played by rolling the block across the board. Only some types of moves are allowed: When the block stands on its 1x1 face, the player may roll the block in either of the four basic directions. However, when the block's bottom face is 2x1, the player may only roll it onto one of its 1x1 faces. In other words, the block must always be rolled over an edge of length 1.
All allowed moves are shown in the figure below. (The old state of the block is always semi-transparent, the new state is opaque.)
So far, the game seems trivial. Its difficulty comes from the fact that there are holes instead of some cells. Whenever the entire bottom face of the block stands on a hole, the block falls through the hole and the player loses the game. The block also falls off if the player rolls it across the edge of the game board. (Note that if the block stands on a 2x1 face and only one of the two cells under the face is missing, the block is still safe. Technically, the block would also be safe with one half of its bottom face sticking out of the game board, but obviously a move into such a configuration will never help you reach the goal.)
Bohn has been playing Block Puzzle too much. Jrus is bored, so he decided to make Bohn's game unsolvable by making more holes into his board. Jrus can only remove cells that are neither starting nor goal. As he doesn't want to get caught, he wants to remove as few cells as possible.
You are given the current board as a
Constraints
- n will be between 3 and 50, inclusive.
- board will contain exactly n elements.
- Each element of board will contain exactly n characters.
- Each character in board will be '.', 'H', 'b' or '$'.
- board will contain exactly one '$' character.
- board will contain at least one 'b' character.
Examples
0)
{"b..$",
"....",
"HHHH",
"HHHH"}
Returns: 2
Remove the two cells between the start and the goal. Note that removing just one of them is not enough.
1)
{"............H..",
"...............",
"...............",
"HHH$HHH.....H..",
"HHHHHHH........",
"HHHHHHHH.......",
"......b..H.....",
"...............",
"...............",
"...H..H..H.....",
"...............",
"...............",
"...............",
"...............",
"..............."}
Returns: 0
This puzzle is already unsolvable.
2)
{"............H..",
"...............",
"...............",
"HHH$HHH........",
"HHHHHHH........",
"HHHHHHHH.......",
"......b..H.....",
"...............",
"...............",
"...H..H..H.....",
"...............",
"...............",
"...............",
"...............",
"..............."}
Returns: 1
This puzzle is solvable. The only difference between this puzzle and Example 1 is that one cell in this example was a hole in Example 1. Hence, we can easily make this puzzle unsolvable by removing that one cell.
3)
{"b..$...",
"...H...",
".......",
"b..b..b",
"...H...",
".......",
"b..b..b"}
Returns: 4
A puzzle may contain multiple starting cells. Bohn may start the game from any of them.
4)
{"b..b..b",
"..b..b.",
".......",
"b..$bbb",
".b.....",
"....b..",
"b..b..b"}
Returns: -1
You cannot replace start cells with holes.
Submissions are judged against all 202 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BlockTheBlockPuzzle with a public method int minimumHoles(vector<string> board) · 202 test cases · 2 s / 256 MB per case