PiecesMover
SRM 425 · 2008-11-12 · by crazyb0y
Problem Statement
You are given a 5x5 board containing at most 5 pieces. Your task is to move the pieces so that the cells occupied by them form a connected component. A connected component is a set of cells where each pair of cells is connected by at least one path. Consecutive cells in a path must all be adjacent. Two cells are called adjacent if they share a common edge.
You are given a String[] board, where the j-th character of the i-th element is '*' if cell (i, j) is occupied by a piece and '.' otherwise. Return the minimum number of moves required to achieve your goal. Each move consists of moving one piece to an adjacent empty cell.
Constraints
- board will contain exactly 5 elements.
- Each element of board will contain exactly 5 characters.
- Each character in board will be either '.' or '*'.
- board will contain between 1 and 5 '*' characters, inclusive.
{".....",
"..**.",
".....",
"...*.",
"....."}
Returns: 1
+ + + + + + + O O + + + + O + | + + + . + + + + + +
{".....",
".....",
".**..",
".*...",
"**..."}
Returns: 0
The cells occupied by pieces have already formed a connected component.
{"*...*",
".....",
".....",
".....",
"*...*"}
Returns: 12
. + +-+-. | | + + + + + | | +-O O O-+ | + O + + + | | .-+ + + .
{"**...",
"*....",
".....",
".....",
"*...*"}
Returns: 7
{"*...*",
".....",
".....",
".....",
"*.*.*"}
Returns: 10
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PiecesMover with a public method int getMinimumMoves(vector<string> board) · 89 test cases · 2 s / 256 MB per case