Viện Robot Voltron đã chế tạo \(n\) robot, đánh số từ \(1\) đến \(n\). Hai robot tương thích khi các nhãn của chúng là hai khoảng số nguyên liên tiếp. Ban đầu mỗi robot chỉ mang một nhãn. Khi nhiều robot hợp nhất, robot tổng hợp mang hai nhãn là nhãn nhỏ nhất và lớn nhất của các robot thành phần. Chẳng hạn, robot \(2\) có thể hợp nhất với robot \(1\) hoặc \(3\); robot \(2\)-\(3\) có thể hợp nhất với robot \(4\)-\(6\) để tạo robot \(2\)-\(6\). Mục tiêu cuối cùng là robot \(1\)-\(n\).

Các robot ở trong một căn phòng dạng lưới \(w\times h\), bao quanh bởi tường. Một số ô bị chặn và robot không thể đi vào. Mỗi robot chiếm đúng một ô, nhưng một ô có thể chứa nhiều robot. Ban đầu các robot ở những ô khác nhau.

Khi được đẩy theo một trong bốn hướng, robot đi thẳng theo hàng hoặc cột cho đến khi bị tường hay ô bị chặn cản lại. Sau khi dừng, nó hợp nhất với mọi robot tương thích cùng ô; quá trình tiếp tục cho tới khi không thể hợp nhất thêm.

Một số ô có bàn xoay theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Khi robot đi vào ô có bàn xoay, hướng chuyển động của nó lập tức quay \(90\) độ theo chiều của bàn. Nếu robot đang đứng trên bàn xoay khi được đẩy, nó quay \(90\) độ trước rồi mới rời ô, do đó hướng chuyển động vuông góc với hướng đẩy.

Tại mỗi thời điểm chỉ một robot được di chuyển. Hãy tìm số lần đẩy ít nhất để hợp nhất tất cả \(n\) robot, hoặc xác định rằng điều đó không thể thực hiện.

Dữ liệu vào

• Dòng đầu chứa \(n,w,h\).
• \(h\) dòng tiếp theo, mỗi dòng gồm \(w\) ký tự mô tả căn phòng:
• chữ số từ 1 đến 9: robot có nhãn tương ứng;
• x: ô bị chặn;
• A: bàn xoay ngược chiều kim đồng hồ;
• C: bàn xoay theo chiều kim đồng hồ;
• .: ô trống.

Dữ liệu ra

In số lần đẩy nhỏ nhất, hoặc -1 nếu không thể hợp nhất tất cả robot.

Ví dụ

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

5

Giải thích

Một phương án tối ưu gồm năm bước:

1. Đẩy robot \(3\) sang phải. Robot gặp bàn xoay ngược chiều kim đồng hồ, chuyển hướng lên trên và dừng trước tường.
2. Đẩy robot \(4\) lên trên. Nó dừng trước tường và hợp nhất với robot \(3\) thành robot \(3\)-\(4\).
3. Đẩy robot \(2\) lên trên. Nó gặp bàn xoay, rẽ ngược chiều kim đồng hồ rồi dừng trước tường.
4. Đẩy robot \(2\) sang phải. Vì đang ở trên bàn xoay, nó chuyển hướng lên trên, dừng ở góc và hợp nhất với robot \(1\) thành robot \(1\)-\(2\).
5. Đẩy robot \(3\)-\(4\) sang trái. Nó dừng ở góc và hợp nhất với robot \(1\)-\(2\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Robots.