Portal™ là một trò chơi giải đố/điều khiển nhân vật góc nhìn thứ nhất được phát triển và phát hành bởi Valve Software. Ý tưởng của trò chơi là tạo ra hai cổng (portal) trên các bức tường, sau đó nhảy qua một cổng và đi ra ở cổng kia. Bài toán này có ý tưởng tương tự nhưng không yêu cầu bạn phải từng chơi Portal.

Trong bài toán này, bạn đang ở trong một lưới kích thước \(R \times C\). Ngoài ra, có một chiếc bánh ngọt thơm ngon ở một vị trí khác trong lưới. Bạn đang rất đói và muốn đến chỗ chiếc bánh với ít lượt di chuyển nhất có thể. Bạn có thể di chuyển lên phía bắc (north), nam (south), đông (east) hoặc tây (west) đến một ô trống. Ngoài ra, bạn có khả năng tạo ra các cổng trên tường.

Để giúp bạn đến chỗ chiếc bánh, bạn có một khẩu súng cổng có thể bắn ra hai loại cổng: cổng màu vàng và cổng màu xanh biển. Một cổng được tạo ra bằng cách bắn súng cổng theo một trong bốn hướng bắc, nam, đông hoặc tây. Súng sẽ phát ra một quả cầu năng lượng và tạo ra một cổng trên bức tường đầu tiên mà nó va chạm. Lưu ý rằng trong bài toán này, việc bắn súng cổng không được tính là một lượt di chuyển. Nếu bạn bắn súng cổng vào chiếc bánh, quả cầu năng lượng sẽ đi xuyên qua nó.

Sau khi tạo ra cả cổng màu vàng và cổng màu xanh biển, bạn có thể đi xuyên qua cổng màu vàng để đến vị trí cổng màu xanh biển hoặc ngược lại. Sử dụng các cổng này, bạn có thể đến chỗ chiếc bánh nhanh hơn nữa! Bạn chỉ có thể sử dụng cổng sau khi đã tạo ra cả hai loại cổng vàng và xanh biển.

Xét lưới sau đây:

Các ô màu xám đại diện cho tường, ô màu trắng đại diện cho ô trống, và vòng tròn màu đỏ chỉ vị trí của bạn.

Giả sử bạn bắn một cổng màu xanh biển về phía đông. Cổng sẽ được tạo ra trên bức tường đầu tiên nó chạm vào, kết quả là:

Bây giờ giả sử bạn bắn một cổng màu vàng về phía nam:

Tiếp theo, bạn di chuyển về phía nam một bước:

Bây giờ đến phần thú vị. Nếu bạn di chuyển về phía nam thêm một bước nữa, bạn sẽ đi xuyên qua cổng màu vàng để đến cổng màu xanh biển:

Tại mỗi thời điểm chỉ có thể có tối đa một cổng màu vàng và một cổng màu xanh biển. Ví dụ, nếu bạn cố gắng tạo một cổng màu xanh biển ở phía tây, cổng màu xanh biển cũ sẽ biến mất:

Một cổng chỉ biến mất khi một cổng khác cùng màu được bắn ra.

Lưu ý rằng các cổng được tạo ra ở một mặt của bức tường. Nếu một bức tường có cổng ở mặt phía đông của nó, bạn phải di chuyển vào bức tường từ phía đông để đi xuyên qua cổng. Nếu không, bạn sẽ chỉ đơn giản là đâm vào tường, điều này là không thể.

Cuối cùng, bạn không được đặt hai cổng chồng lên nhau. Nếu bạn cố bắn một cổng vào mặt của một bức tường đã có sẵn một cổng (bất kể màu gì), cổng thứ hai sẽ không được hình thành.

Cho bản đồ mê cung, vị trí ban đầu của bạn và vị trí của chiếc bánh, bạn cần tìm số lượt di chuyển tối thiểu để đến chỗ chiếc bánh nếu có thể. Hãy nhớ rằng việc bắn súng cổng không tính là một lượt di chuyển.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). \(N\) bộ test tiếp theo.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên \(R\) và \(C\) cách nhau bởi một khoảng trắng. \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) ký tự, đại diện cho bản đồ:

• . biểu thị một ô trống;
• # biểu thị một bức tường;
• O biểu thị vị trí bắt đầu của bạn; và
• X biểu thị vị trí của chiếc bánh.

Sẽ có chính xác một ký tự O và một ký tự X trong mỗi bộ test.
Các ô nằm ngoài lưới đều được coi là tường và bạn có thể sử dụng chúng để tạo cổng.

Dữ liệu ra

Với mỗi bộ test, bạn nên xuất ra một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ test và \(Y\) là số lượt di chuyển tối thiểu để đến chỗ chiếc bánh hoặc "THE CAKE IS A LIE" nếu không thể đến được chỗ chiếc bánh.

Ràng buộc

• Thời gian giới hạn: 30 giây mỗi bộ test.
• Bộ nhớ giới hạn: 1GB.

Phân nhóm

• Small dataset (Test set 1): \(N = 200\); \(1 \le R, C \le 8\).
• Large dataset (Test set 2): \(N = 50\); \(1 \le R, C \le 15\).

Đ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ụ

3
4 7
.O..##.
.#.....
.#.####
.#...X.
5 5
O....
.....
.....
.....
....X
1 3
O#X

Case #1: 4
Case #2: 2
Case #3: THE CAKE IS A LIE

Nguồn

Google Code Jam 2008, Vòng 3, bài Portal.

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