CSES - Swap Game | Trò chơi hoán đổi

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cung cấp một lưới \(3 × 3\) chứa các số \(1,2,…, 9\). Nhiệm vụ của bạn là thực hiện một chuỗi các bước di chuyển để lưới trở về dạng như sau:

$
\begin{matrix}
1 \ \ 2 \ \ 3 \
4 \ \ 5 \ \ 6 \
7 \ \ 8 \ \ 9
\end{matrix}
$

Trên mỗi lần di chuyển, bạn có thể hoán đổi các số trong hai ô vuông liền kề bất kỳ (theo chiều ngang hoặc chiều dọc). Số lần di chuyển cần thiết tối thiểu là bao nhiêu?

Input

  • Gồm ba dòng, mỗi dòng gồm ba số nguyên.

Output

  • In ra đáp án là số lần di chuyển ít nhất.

Example

Sample input

2 1 3
7 5 9
8 4 6

Sample output
4


Bình luận


  • 0
    nguyen_ducminh 12:31 a.m. 31 Tháng 8, 2023 đã chỉnh sửa

    CSES - Swap Game | Trò chơi hoán đổi

    Bạn được cho tấm lưới \(3 \times 3\) chứa các số \(1, 2, ..., 9\). Nhiệm vụ của bạn là thực hiện một chuỗi các bước di chuyển để tấm lưới có dạng như sau:

    1 2 3
    4 5 6
    7 8 9

    Tại mỗi bước, bạn có thể hoán đổi vị trí của 2 ô kề cạnh bất kì (theo chiều ngang hoặc dọc). Số bước di chuyển cần thiết tối thiểu là bao nhiêu?

    Input

    • Gồm ba dòng, mỗi dòng gồm ba số nguyên.

    Output

    • Gồm một số nguyên là số bước di chuyển tối thiểu.

    Example

    Test 1

    Input
    2 1 3
    7 5 9
    8 4 6
    Output
    4