Sokoban là trò chơi Nhật Bản, tên gọi có nghĩa là “người giữ kho”. Bạn phải đẩy các thùng tới ô đích. Muốn đẩy một thùng, cả ô phía sau (nơi đứng) và ô phía trước nó phải trống. Mỗi lần chỉ đẩy một thùng; không được đẩy thùng hay đứng ra ngoài bàn.

Trong hình, thùng 1 đẩy được theo bốn hướng; thùng 2 chỉ theo đông hoặc tây vì ô phía nam không trống; thùng 3 không đẩy được; thùng 4 chỉ theo đông hoặc tây vì có tường phía nam.

Sokoban đã được chứng minh là một bài toán đầy đủ PSPACE, nhưng ở đây ta xét một biến thể dễ hơn. Sokoban đã được chứng minh là một bài toán đầy đủ PSPACE, nhưng ở đây ta xét một biến thể dễ hơn. Ở biến thể này, các thùng chứa nam châm mạnh và gần như luôn phải dính nhau. Trạng thái ổn định nghĩa là mọi thùng liên thông qua cạnh. Nếu một lần đẩy làm chúng mất liên thông, ta vào chế độ nguy hiểm và lần đẩy kế tiếp bắt buộc khôi phục liên thông.

Nếu đẩy thùng phía bắc sang tây, ta vào chế độ nguy hiểm:

Sau đó có thể đẩy chính thùng ấy xuống nam để ổn định lại:

Cho bàn, cấu hình ban đầu và cấu hình đích. Hãy tìm số lần đẩy thùng ít nhất, hoặc kết luận không thể giải. Cả cấu hình đầu và cuối đều không nguy hiểm. Người giữ kho có thể nhảy tức thời tới bất kỳ ô trống nào.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(R,C\), rồi \(R\) dòng, mỗi dòng \(C\) ký tự: . ô trống, # tường, x đích, o thùng, w vừa là thùng vừa là đích. Số thùng bằng số đích.

Dữ liệu ra

In Case #X: K, với \(K\) là số lần đẩy nhỏ nhất, hoặc -1 nếu không thể giải.

Ràng buộc

• \(1 \le T \le 50\), \(1 \le R,C \le 12\); bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: 1–2 thùng.
• Lớn: 1–5 thùng.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
5 4
....
#..#
#xx#
#oo#
#..#
7 7
.######
.x....#
.x....#
..#oo.#
..#...#
.######
.######
4 10
##########
#.x...o..#
#.x...o..#
##########
3 4
.#x.
.ow.
....

Case #1: 2
Case #2: 8
Case #3: 8
Case #4: 2

Nguồn

Google Code Jam 2009, Vòng 3, bài EZ-Sokoban.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.