Bò rất say mê cờ đam. Tuy chơi vô cùng vui, chúng rất kém ở tàn cuộc và cần giúp đỡ.
Với bàn $N\times N$, $(4 \le N \le 30)$, tìm chuỗi tối ưu kết thúc ván ở lượt kế tiếp. Quân chỉ đi trên + và ăn bằng nhảy qua quân đối phương, bị bỏ ngay. Ví dụ $N=8$:
- + - + - + - + + - + - + - + - - + - K - + - + + - + - + - + - - o - o - + - + + - K - + - + - - o - + - + - + + - K - + - K -
K là vua của Bessie, o là quân đối phương. Bessie luôn đi tiếp. Vua nhảy liên tiếp qua đối phương theo bất kỳ hướng chéo nào và bỏ quân bị ăn. Ở bàn này vua dưới bên trái nhảy qua cả ba đối phương, kết thúc ván. K đang đi được đánh dấu >K<.
- + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - - + - K - + - + - + - K - + - + - + - K - + - + - + - K - + - + + - + - + - + - + - + - + - + - + ->K<- + - + - + - + - + - + - - o - o - + - + - o - o - + - + - + - o - + - + - + - + - + - + + - K - + - + - >K<- K - + - + - + - K - + - + - + - K ->K<- + - - o - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + + ->K<- + - K - + - + - + - K - + - K - + - K - + - K - + - K -
Từ trái sang phải: ban đầu, sau bước 1, sau bước 2, sau bước 3.
Các bước đi qua các ô sau:
1 2 3 4 5 6 7 8 1 - + - + - + - + 2 + - + - + - + - 3 - + - K - + - + 4 + - * - + - + - 5 - o - o - + - + 6 * - K - * - + - 7 - o - + - + - + 8 + - K - + - K -
Hàng, cột; bắt đầu: $(8,3)$; bước đi: $(6,1)$, $(4,3)$, $(6,5)$.
Tìm chuỗi kết thúc ván cho bàn đầu vào $N\times N$ nếu có (thực ra là duy nhất). Có ít nhất một quân vua và một quân đối phương.
Dữ liệu vào
Dòng 1: số nguyên $N$.
Dòng $2,\ldots,N+1$: dòng $i+1$ có $N$ ký tự
-,+,Khoặco, mô tả hàng $i$ của bàn hợp lệ.
Dữ liệu ra
- Từ dòng 1: nếu không thể, in
impossibleriêng một dòng. Nếu có, mỗi dòng hai số nguyên cách nhau bởi khoảng trắng, vị trí liên tiếp của quân vua đi như vậy sẽ thắng.
Ví dụ
Dữ liệu vào 1
8 -+-+-+-+ +-+-+-+- -+-K-+-+ +-+-+-+- -o-o-+-+ +-K-+-+- -o-+-+-+ +-K-+-K-
Dữ liệu ra 1
8 3 6 1 4 3 6 5
Tác giả bài toán: Rob Kolstad, 2008