시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB30171553.571%

문제

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:

$1$ $2$
$3$

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:

$2$
$1$ $3$

After $1$ move:

$2$
$1$ $3$

After $2$ moves:

$1$ $2$
$3$

After $3$ moves:

$1$ $2$
$3$

입력

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.

예제 입력 1

2-
13

예제 출력 1

3

예제 입력 2

-3
21

예제 출력 2

6

출처

School > CS@Mines > CS@Mines HSPC 2022 > Beginner I번

  • 문제를 만든 사람: Adam Sandstedt