34388번 - 3-Puzzle 다국어

문제

Your friend needs help solving a 15ドル$-Puzzle, so to warm up, you solve the 3ドル$-Puzzle instead. A 3ドル$-Puzzle consists of a 2ドル \times 2$ grid containing 3ドル$ tiles numbered 1ドル$ through 3ドル$ and one empty space. The goal is to slide the tiles around so that they are in ascending row-major order and the empty space is on the bottom right like this:

Given the starting position of a 3ドル$-Puzzle, find the minimum number of moves it takes to solve the puzzle. Here's an example of how sample input 1ドル$ can be solved in 3ドル$ moves:

Starting position:

After 1ドル$ move:

After 2ドル$ moves:

After 3ドル$ moves:

입력

The input will consist of exactly 2ドル$ lines, each containing exactly 2ドル$ characters.

Each character is either a number 1ドル$ through 3ドル$ (representing one of the tiles) or a dash (-) (the empty space).

The puzzle state represented by the input is guaranteed to be a solvable configuration.

출력

Output a singe integer, indicating the minimum number of moves required to solve the puzzle from the provided starting position, or 0ドル$ if it's already in the solved position.

제한

노트