Solitaire

Interview

Time limit1sMemory limit128 MB

Summary
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 8×88 \times 8 chessboard. The rows and columns are numbered from 11 to 88 — 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 44, column 44 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 88 moves.

Input

Two lines, each describing one configuration of the four pieces.

Each line holds 88 integers a1,a2,…,a8a_1, a_2, \ldots, a_8 separated by single spaces. For every jj with 1≤j≤41 \le j \le 4, the pair (a2j−1,a2j)(a_{2j-1}, a_{2j}) gives the row and column of one piece. Every coordinate lies between 11 and 88, 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 88 moves, and NO otherwise.

Examples2

  1. Example 1

    Input
    4 4 4 5 5 4 6 5
    2 4 3 3 3 6 4 6
    
    Expected output
    YES
    
  2. Example 2

    Input
    1 1 1 2 2 1 2 2
    7 7 7 8 8 7 8 8
    
    Expected output
    NO