2464. Checkers

单点时限: 2.0 sec

内存限制: 256 MB

The cows have taken up the game of checkers with a vengeance.Unfortunately, despite their infinite enjoyment of playing, they are terrible at the endgame. They want your help.

Given an NxN (4 <= N <= 30) checkboard, determine the optimal set of moves to end the game on the next move. Checkers move only on the ‘+’ squares and capture by jumping ‘over’ an opponent’s piece. The piece is removed as soon as it is jumped. See the example below

where N=8:

                • The K’s mark Bessie’s kings; the o’s represent the
                • opponent’s checkers. Bessie always moves next. The
      • K - + - + Kings jump opponent’s checkers successively in any
                • diagonal direction (and removes pieces when jumped).
  • o - o - + - +

    • K - + - + - For this board, the solution requires the lower left
  • o - + - + - + King to jump successively across all three of the

    • K - + - K - opponents’ checkers, thus ending the game (moving K

marked as >K<):

Original

              • +
              • -
      • K - + - +
              • -
  • o - o - + - +

    • K - + - + -
  • o - + - + - +

  • ->K<- + - K -

After move 1

              • +
              • -
      • K - + - +
              • -
  • o - o - + - +

K<- K - + - + -

              • +
            • K -

After move 2

              • +
              • -
      • K - + - +
  • ->K<- + - + -

      • o - + - +
    • K - + - + -
              • +
    • K - + - K -

After move 3

              • +
              • -
      • K - + - +
              • -
              • +
    • K ->K<- + -
              • +
    • K - + - K -

The moves traversed these squares:

1 2 3 4 5 6 7 8 R C

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 -

Write a program to determine the (unique, as it turns out) game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board.

输入格式

  • Line 1: A single integer: N

  • Lines 2..N+1: Line i+1 contains N characters (each one of: ‘-‘, ‘+’,

‘K’, or ‘o’) that represent row i of a proper checkboard.

输出格式

  • Lines 1..?: If this sequence of moves is impossible, output

“impossible” on a line by itself. If such a sequence exist,

each line contains two space-separated integers that represent

successive locations of a king whose moves will win the game.

样例

Input
8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-
Output
8 3
6 1
4 3
6 5

0 人解决,4 人已尝试。

0 份提交通过,共有 19 份提交。

9.9 EMB 奖励。

创建: 15 年,1 月前.

修改: 6 年,7 月前.

最后提交: 3 年,4 月前.

来源: USACO 2008 DEC

题目标签