Solitaire
InterviewTime limit1sMemory limit128 MB
Given two placements of four identical pieces on an 8x8 board, decide whether slides and jumps reach the second from the first within 8 moves.
- Level
Medium7 of 10
- Topics
- BFS, Graph, Hash map, Implementation
- Solved
- No attempts yet
Problem
Solitaire is a game played on an chessboard. The rows and columns are numbered from to — rows from top to bottom, columns from left to right.
Four identical pieces sit on the board. In a single move you may either:
- slide a piece onto an empty orthogonally adjacent field (up, down, left, or right), or
- jump a piece over exactly one occupied orthogonally adjacent field, landing on the empty field immediately beyond it (up, down, left, or right).

In the configuration above, the piece at row , column has four legal moves: one row up, two rows down (jumping the piece directly below it), one column left, or two columns right (jumping the piece directly to its right).
Given two configurations, decide whether the second one can be reached from the first in at most moves.
Input
Two lines, each describing one configuration of the four pieces.
Each line holds integers separated by single spaces. For every with , the pair gives the row and column of one piece. Every coordinate lies between and , and within a configuration the four pieces occupy four distinct fields.
Output
Print YES if the second configuration is reachable from the first in at most moves, and NO otherwise.