Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QTMOVE - Trò chơi xếp hình

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274830/problem/C

 

Cho một bảng kích thước MxN được chia thành MxN ô, mỗi ô có 1 viên bi được đánh số từ 1 đến M*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≤100, trong đó 60% số test có M,N≤10.

Examples

Input:

3 3

1 2 3

5 0 6

4 7 8

Output:

4

Giải thích:

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


Được gửi lên bởi:continue......
Ngày:2012-12-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Đinh Quang Hiếu

hide comments
2016-09-08 11:55:35
Bfs
2014-08-25 15:50:46 trung thien
ai làm rồi nào....đệ quy thì mệt đây
2013-12-17 15:26:28 IN GOD WE TRUST
:xephinh:
2012-12-13 01:22:09 Erik
Xếp hính xếp hình :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.