Problem Statement |
| | Teddy and Tracy are on school vacation, so they bought a puzzle book. Within the book, they discovered an interesting game called Solitaire Chess.
The game of Solitaire Chess is played on an 8 x 8 board consisting of 64 unit squares. The rows are labeled '1' through '8' from bottom to top, and the columns are labeled 'a' through 'h' from left to right. Squares are notated as "cr" (quotes for clarity), where c is the column and r is the row.
There are two kinds of pieces in Solitaire Chess: the knight, represented by the character 'N', and the pawn, represented by the character 'P'. The legal moves of each piece are shown in the diagrams below.
abcdefgh abcdefgh
8 ........ 8 ........
7 ..X.X... 7 ........
6 .X...X.. 6 ........
5 ...N.... 5 ...X....
4 .X...X.. 4 ...P....
3 ..X.X... 3 ........
2 ........ 2 ........
1 ........ 1 ........
Knight Pawn
In a single move, a knight can move to any one of the eight 'X' squares appearing in the left diagram, while a pawn can move to the single 'X' square appearing in the right diagram. All moves are relative to the current piece location and apply for all piece locations, provided the piece doesn't move outside the board. Moreover, a square may contain more than one piece.
If a pawn moves to the eighth row, it is immediately promoted into a knight. The promotion itself doesn't count as a move.
You are given two String[]s board1 and board2. board1 is the initial layout of the board and board2 is the desired final layout of the board. Character j of element i of board1 and board2 is 'P' if a pawn is located on the corresponding square, 'N' if a knight is located on the corresponding square, or '.' if the corresponding square is empty.
Return the minimum number of moves required to transform the initial layout into the desired layout, or -1 if it is impossible. |
| |
Definition |
| | | Class: | SolitaireChess | | Method: | transform | | Parameters: | String[], String[] | | Returns: | int | | Method signature: | int transform(String[] board1, String[] board2) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Elements 0 through 7 of both board1 and board2 correspond to rows '8' through '1', respectively. |
| - | Characters 0 through 7 of each element of both board1 and board2 correspond to columns 'a' through 'h', respectively. |
| |
Constraints |
| - | board1 and board2 will each contain exactly 8 elements. |
| - | Each element of both board1 and board2 will contain exactly 8 characters. |
| - | Each character of each element of both board1 and board2 will be one of '.', 'P', and 'N'. |
| - | Element 0 of both board1 and board2 will not contain the character 'P'. |
| - | board1 and board2 will each contain at most 20 pieces as described above. |
| |
Examples |
| 0) | |
| | {"...N....",
"........",
"........",
"........",
"........",
"........",
"...P....",
"........"} | {"...N....",
".....N..",
"........",
"........",
"........",
"........",
"........",
"........"} |
| Returns: 7 | | Move the pawn on d2 to d8 (6 moves), promoting it into a knight. Then move one of the knights on d8 to f7. |
|
|
| 1) | |
| | {"........",
"........",
"...P....",
"........",
"........",
"........",
"........",
"........"} | {"........",
"........",
"........",
"........",
"........",
"........",
"........",
"...P...."} |
| Returns: -1 | | A pawn cannot move backward. |
|
|
| 2) | |
| | {"........",
"........",
"........",
"........",
"........",
"........",
"........",
".N...P.."} | {"........",
"........",
"........",
"........",
"........",
"........",
".....P..",
".......N"} |
| Returns: 5 | One optimal solution is:
- Move the pawn on f1 to f2.
- Move the knight on b1 to c3.
- Move the knight on c3 to e2.
- Move the knight on e2 to g3.
- Move the knight on g3 to h1.
|
|
|
| 3) | |
| | {"N.......",
"........",
"N.......",
"........",
"........",
"........",
"........",
"........"} | {"........",
"..N.....",
"........",
"........",
"........",
"........",
"........",
"........"} |
| Returns: -1 | |
|
| 4) | |
| | {"..N.N...",
"PPP....N",
"..N..N..",
"N...N...",
"...NNNNN",
"N.......",
"...NN...",
"..N...N."} | {"..N....N",
"P....N..",
"..N..N..",
"N..NNN.N",
"N.....N.",
"N.N.....",
"...NNN..",
".....N.N"} |
| Returns: 23 | |
|