QTMOVE - Trò chơi xếp hình
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: code123
- Nguồn bài: Ðinh Quang Hiếu