Trò chơi xếp hình

View as PDF

Submit solution

Points: 1.70 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ðinh Quang Hiếu
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bảng kích thước ~M \times N~ được chia thành ~M \times N~ ô, mỗi ô có ~1~ viên bi được đánh số từ ~1~ đến ~M \times N-1~, không có ~2~ viên bi nào có số giống nhau, có duy nhất ~1~ ô trống, được kí hiệu bằng số ~0~. Ban đầu, các viên được sắp xếp theo thứ tự từ trái sang phải, từ trên xuống dưới, ô ở vị trí ~[M~, ~N]~ là ô trống.

VD: ~M = N = 3~

~1~ ~2~ ~3~
~4~ ~5~ ~6~
~7~ ~8~ ~0~

Một viên bi có thể di chuyển sang ~1~ trong ~4~ ô kề cạnh nếu ô đó là ô trống và không được di chuyển ra khỏi bảng. Người ta di chuyển một số viên bi của bảng. Hãy tính xem cần ít nhất bao nhiêu lần di chuyển để bảng trở về lại như ban đầu.

Input

Dòng đầu gồm ~2~ số ~M~, ~N~.

~M~ dòng sau, mỗi dòng gồm ~N~ số là trạng thái của bảng hiện tại.

Output

Gồm ~1~ dòng duy nhất là số lần di chuyển ít nhất để bảng trở về trạng thái ban đầu.

Giới hạn

~M, N \leq 100~, trong đó ~60\%~ số test có ~M, N \leq 10~.

Sample Input

3 3
1 2 3
5 0 6
4 7 8

Sample Output

4

Note

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

5 0 6   ->       0 5 6   ->       4 5 6   ->       4 5 6   ->       4 5 6

4 7 8            4 7 8            0 7 8            7 0 8            7 8 0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.