Đây là một bài toán tương tác.
Taja có thể dễ dàng chiến thắng trò chơi này, nhưng tất cả bạn bè của cô ấy thì không. Bây giờ cô ấy mời bạn chơi trò chơi này.
Thiết bị trò chơi bao gồm một lưới $n \times n$ ($5 \le n \le 40$), một quân cờ, hai đồng xu (COIN1, COIN2), hai con xúc xắc với các hướng chính (DICE1, DICE2), và rất nhiều khối có kích thước bằng một ô.
| Tên | Số mặt | Các mặt |
|---|---|---|
| COIN1. Đồng xu di chuyển | 2 | SLIDE, RAM |
| COIN2. Đồng xu sửa đổi | 2 | PLACE, REMOVE |
| DICE1. Xúc xắc hướng 1 | 4 | N (Bắc), S (Nam), W (Tây), E (Đông) |
| DICE2. Xúc xắc hướng 2 | 8 | N (Bắc), S (Nam), W (Tây), E (Đông), NW (Tây Bắc), NE (Đông Bắc), SW (Tây Nam), SE (Đông Nam) |
Trước khi bắt đầu trò chơi, quân cờ và một số khối được đặt trên lưới. Sau đó, người chơi thực hiện các lượt đi. Đầu tiên, người chơi chọn một đồng xu và tung nó để xác định hành động. Sau đó, người chơi chọn một trong các con xúc xắc và tung nó để xác định hướng $dir$. Sau đó, một trong bốn hành động sau sẽ xảy ra:
| Chuỗi đồng xu | Hành động |
|---|---|
| SLIDE | Di chuyển quân cờ dọc theo các ô trống theo hướng $dir$, cho đến khi quân cờ va chạm với một khối hoặc biên của mê cung |
| RAM | Di chuyển quân cờ dọc theo các ô trống theo hướng $dir$, cho đến khi va chạm với khối đầu tiên. Sau đó di chuyển quân cờ và khối đó theo cùng hướng, cho đến khi khối đang di chuyển va chạm với một khối khác hoặc biên của lưới |
| PLACE | Nếu ô liền kề theo hướng $dir$ tiếp theo quân cờ là ô trống và nằm trong lưới, đặt một khối vào ô này |
| REMOVE | Nếu ô liền kề theo hướng $dir$ tiếp theo quân cờ chứa một khối và nằm trong lưới, loại bỏ khối khỏi ô này |
Mục tiêu là đưa quân cờ đến ô đích. Một truy vấn cho bài toán này là một lần tung đồng xu và một lần tung xúc xắc.
Giao tiếp
Đầu tiên, bộ tương tác cung cấp kích thước của mê cung, mê cung và tọa độ của ô đích. Sau đó, các hành động 4 bước sau sẽ xảy ra:
- Chương trình của giám khảo hiển thị tọa độ của quân cờ hoặc thông báo rằng quân cờ đã đến ô đích.
- Chương trình của bạn hiển thị tên đồng xu.
- Chương trình của giám khảo hiển thị tên hành động trên đồng xu.
- Chương trình của bạn hiển thị tên xúc xắc.
- Chương trình của giám khảo hiển thị tên hướng trên xúc xắc và thông tin bổ sung cho hành động "RAM".
Dữ liệu ra
Dữ liệu ra tiêu chuẩn nên bao gồm một cặp dòng: tên đồng xu và tên xúc xắc. Tên đồng xu là chuỗi "COIN1" hoặc "COIN2". Tên xúc xắc là chuỗi "DICE1" hoặc "DICE2". Đừng quên xóa bộ đệm đầu ra tiêu chuẩn (flush) sau khi in mỗi dòng.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào tiêu chuẩn chứa một số nguyên $n$ — kích thước của mê cung. $n$ dòng tiếp theo chứa $n$ ký tự "." (ASCII 46) hoặc "#" (ASCII 35), biểu thị ô trống và ô có khối tương ứng. Dòng tiếp theo chứa hai số nguyên $r_f$ và $c_f$ — số hàng và số cột của ô đích. Góc trên bên trái là $(1, 1)$, góc dưới bên phải là $(n, n)$. Ô đích và ô ban đầu là các ô trống.
Các nhóm tiếp theo mô tả mỗi lượt đi:
- Dòng đầu tiên của một nhóm chứa hai số nguyên $r, c$ — số hàng và số cột của quân cờ, hoặc $(-1, -1)$ nếu quân cờ đã đến ô đích.
- Dòng tiếp theo chứa tên hành động hiển thị trên đồng xu.
- Dòng tiếp theo chứa tên hướng hiển thị trên xúc xắc.
- Nếu hành động hiện tại là "RAM", hai chuỗi tiếp theo chứa hai số nguyên $r_1, c_1$ và $r_2, c_2$, biểu thị quân cờ va chạm với một khối tại tọa độ $(r_1, c_1)$ và di chuyển khối đó đến ô $(r_2, c_2)$.
Hướng Bắc tương ứng với số hàng giảm dần. Hướng Nam tương ứng với số hàng tăng dần. Hướng Tây tương ứng với số cột giảm dần. Hướng Đông tương ứng với số cột tăng dần. Mỗi mặt của bất kỳ đồng xu hoặc xúc xắc nào đều xuất hiện với xác suất như nhau.
Ví dụ
Dữ liệu vào 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
Dữ liệu ra 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1