Chơi cờ

View as PDF

Submit solution

Points: 1.90 (partial)
Time limit: 0.25s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO December 2008 - Gold Division
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Tụi bò rất thích chơi cờ và chơi cờ với niềm say mê vô bờ. Nhưng thật đáng tiếc, dù chúng rất thích chơi cờ, chúng lại chơi quá kém và muốn nhờ bạn giúp chúng.

Cho ~1~ bàn cờ kích thước ~N \times N~. Các quân cờ chỉ di chuyển trên các ô '+' và ăn quân đối phương khi nhảy qua ~1~ quân cờ của đối phương, quân cờ bị ăn sẽ bị loại ra khỏi bàn cờ. Ví dụ sau đây là ~1~ một bàn cờ kích thước ~8 \times 8~:

- + - + - + - +  K là ký hiệu quân Vua của Bessie; o là ký hiệu quân
+ - + - + - + -  cờ của đối phương. Bessie được đi trước và sẽ chọn ra 
- + - K - + - +  1 quân Vua để di chuyển. Quân Vua sẽ nhảy chéo liên 
+ - + - + - + -  tục qua đầu các quân cờ của đối phương (và loại các quân 
- o - o - + - +  đối phương ra khỏi bàn cờ mỗi khi nhảy qua).
+ - K - + - + -  Với bàn cờ này, cách đi tốt nhất sẽ là dùng quân Vua ở góc trái 
- o - + - + - +  dưới nhảy liên tục qua đầu tất cả 3 quân cờ của đối phương, và 
+ - K - + - K -  như vậy trò chơi sẽ kết thúc (di chuyển quân Vua
                 đánh dấu là >K<):

   Ban đầu            Sau bước 1         Sau bước 2          Sau bước 3
- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - + - + - K -     + - + - + - K -

Như vậy các bước đi của quân Vua đi qua các ô sau:

  1 2 3 4 5 6 7 8           Dòng Cột
1 - + - + - + - +    start: 8    3
2 + - + - + - + -    move:  6    1
3 - + - K - + - +    move:  4    3
4 + - * - + - + -    move:  6    5
5 - o - o - + - +
6 * - K - * - + - 
7 - o - + - + - + 
8 + - K - + - K -

Viết chương trình xác định xem Bessie có thể tìm ra một cách di chuyển duy nhất một quân vua và ăn hết tất cả quần cờ của đối phương hay không. Có ít nhất ~1~ quân vua và ~1~ quân cờ đối phương trên bàn cờ.

Input

Dòng ~1~: Một số nguyên: ~N~ ~(4 \le N \le 500)~.

Dòng ~2 \dots N+1~: Dòng ~i+1~ chứa ~N~ ký tự (các ký tự có thể là: '-', '+', 'K', hoặc 'o') biểu diễn dòng ~i~ của bàn cờ.

Dòng ~2~ luôn bắt đầu bằng một ký tự '-'.

Output

Dòng ~1 \dots ?~: Nếu Bessie không thể kết thúc trận đấu trong lượt của mình, ghi ra "impossible" trên ~1~ dòng. Ngược lại, dòng đầu ghi ra vị trí của quân vua được chọn, các dòng còn lại ghi ra vị trí của quân Vua sau các bước di chuyển. Có nhiều phương án thì in ra phương án bất kì.

Sample Input

8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

Sample Output

8 3
6 1
4 3
6 5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.