TwoKings
SRM 243 · 2005-05-17 · by Olexiy
SRM 243 · 2005-05-17 · by Olexiy · Simulation
Problem Statement
Problem Statement
A white queen and two black kings are placed on a 100 x 100 chessboard. White and black sides move by turns. The white queen moves first (only one of the two black kings is moved on each turn). Given three String s, queen, king1 and king2, return the minimal number of white moves needed to capture one of the kings (kings are not allowed to capture the queen, and may not move to the queen's location). queen, king1 and king2 will each contain the 0-based row and column of the corresponding piece.
Notes
- The black side tries to avoid capturing as long as possible.
- Kings move one cell in any direction, horizontally, vertically, or diagonally.
- The queen moves any number of cells in any direction, horizontally, vertically, or diagonally.
- The queen captures a king if it moves to the cell that the king occupies.
- Neither side can skip a turn.
- Pieces may not move off the board.
Constraints
- queen, king1 and king2 will each contain two space-delimited integers between 0 and 99, inclusive.
- The numbers in queen, king1 and king2 will not contain leading zeroes.
- No two pieces will occupy the same cell.
Examples
0)
"0 0" "1 1" "99 99" Returns: 1
You can capture a king on the first turn.
1)
"0 0" "99 0" "0 99" Returns: 1
You can capture any king on the first turn.
2)
"1 1" "90 0" "0 30" Returns: 2
3)
"98 98" "0 97" "99 0" Returns: 2
You can move to the "0 0" cell and threaten both kings. You will capture one of them on the next turn.
4)
"99 0" "1 1" "0 98" Returns: 2
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TwoKings with a public method int captureKing(string queen, string king1, string king2) · 60 test cases · 2 s / 256 MB per case