Gomoku: Minimal Winning Moves for Black

Gomoku (a.k.a. Five in a Row) is a well‐known board game played on a 15×15 grid. Two players alternately place black and white stones on the board (black moves first). Once a stone is placed it cannot be removed. For simplicity, in this problem, assume there are no forbidden moves.

A player wins when they achieve a contiguous line of 5 (or more) stones horizontally, vertically, or diagonally (in both 45° and 135° directions). Given an endgame board configuration where it is Black’s turn, your task is to determine:

• The minimum number of moves needed for Black to win.
• All distinct next moves (i.e. board positions) that will lead to a win in that minimum number of moves.

Note: In this problem, you only need to consider immediate winning moves – that is, moves that produce 5 in a row immediately (resulting in a win in 1 move). It is guaranteed that if a winning move exists, it will win in 1 move, and the board configuration will be such that Black can win immediately by placing a stone on an empty cell.

inputFormat

The input consists of exactly 15 lines, each line representing a row of the board. Each line is a string of 15 characters. The characters can be:

• 'B' for a black stone
• 'W' for a white stone
• '.' for an empty cell

It is guaranteed that it is Black's turn to move.

outputFormat

The output should be formatted as follows:

1. On the first line, output an integer representing the minimum number of moves required for Black to win. (For this problem, it will be 1 if there is an immediate winning move, or -1 if no winning move exists.)
2. On the second line, output an integer representing the number of winning next moves.
3. Then, for each winning next move, output a line with two integers separated by a space. These integers represent the row and column (both 1-indexed) of the cell where Black should place a stone. The moves should be listed in increasing order first by row and then by column.

sample

...............
...............
...............
...............
....BBBB.......
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............

1
2
5 4
5 9