Optimal Checkers Endgame Sequence

The cows have taken up the game of checkers with a vengeance. However, despite their unlimited enjoyment, they are terrible at the endgame and now need your help. Given an \(N\times N\) board (with \(4 \le N \le 500\)) describing a checkers board, determine the optimal sequence of moves (i.e. the smallest number of moves) that ends the game immediately by capturing all opponent pieces in a single sequence.

The board is composed of non‐playable squares denoted by a dash (-) and playable squares denoted by a plus (+). Bessie’s kings are marked by K on playable squares, and the opponent’s checkers are marked by o (which always lie on playable squares as well). Kings move diagonally on playable squares only, and they capture an opponent piece by jumping over it to an empty playable square on the opposite side. Captured pieces are removed immediately when jumped over. It is guaranteed that there is at least one king and at least one opponent piece on the board. Moreover, during the optimal sequence the king may capture an opponent on every move.

Below is an illustrative example for an 8x8 board:

- + - + - + - +    (Row 1)
+ - + - + - + -    (Row 2)
- + - K - + - +    (Row 3)
+ - + - + - + -    (Row 4)
- o - o - + - +    (Row 5)
+ - K - + - + -    (Row 6)
- o - + - + - +    (Row 7)
+ - K - + - K -    (Row 8)

For this board, the optimal solution is to use the lower left king (initially at row 8, column 3) to capture all three opponent pieces in a sequence of jumps. The moves are as follows (each pair represents the row and column, 1-indexed):

8 3
6 1
4 3
6 5

Your task is to write a program to determine such a game‐ending sequence if it exists. If multiple sequences exist, you must output the one with the fewest moves. If no complete sequence exists, output impossible.

Note: All formulas are given in \(\LaTeX\) format. For example, the board size constraint is given by \(4 \le N \le 500\).

POINTS: 330

inputFormat

The first line contains an integer \(N\) denoting the size of the board. The next \(N\) lines each contain \(N\) tokens (separated by spaces) representing the board. The board consists of characters -, +, K, and o, where + denotes a playable square. K denotes one of Bessie's kings and o denotes an opponent piece. It is guaranteed that there is at least one king and at least one opponent piece on the board.

outputFormat

If a game‐ending sequence exists, output the sequence of moves with each move on a new line in the form of two space‐separated integers representing the row and column (1-indexed) of the king’s position after each jump. The first line should be the starting position of the king, followed by positions after each jump. If no valid sequence exists, output impossible.

sample

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

8 3
6 1
4 3
6 5