Description

Gomoku is a widely played board game. On a $15\times 15$ board, two players play with black and white stones (similar to Go). Black moves first. Once a stone is placed, it cannot be lifted; that is, there are no moving or capturing moves.

To simplify the problem, assume there are no “forbidden moves” for Black. “Forbidden moves” is a Gomoku term referring to places where a move is not allowed. When a player first forms a connected line of $5$ stones in one of the horizontal, vertical, $45$-degree diagonal, or $135$-degree diagonal directions, that player wins.

Consider an endgame position with Black to move. Please output the minimum number of moves for Black to win and all distinct next moves that allow Black to win in that number of moves.

Input Format

There are $15$ lines, each containing $15$ integers separated by a space. Let the integer in the $i$-th row and the $j$-th column be $v_{i,j}$. Use $v_{i,j}=0,1,2$ to indicate that the position at row $i$, column $j$ is empty, has a black stone, or has a white stone, respectively. Input is given from the top-left corner, in left-to-right and top-to-bottom order. That is, the first integer $v_{1,1}$ represents the state of row $1$, column $1$, and the last integer $v_{15,15}$ represents the state of row $15$, column $15$.

Output Format

The first line contains two integers $a$ and $b$, where $a$ is the minimum number of moves for Black to win, and $b$ is the number of distinct next moves by which Black can win in $a$ moves.

From the second line to the $(b+1)$-th line, each line contains two integers that represent a row $i$ and a column $j$ for one such next move by Black that leads to a win in $a$ moves. These moves must be sorted in ascending order by $15\times i+j$.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 2 0 2 0 0 0 0 0
0 0 0 0 0 0 2 1 1 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 1 0 0 0 0 0
0 0 0 0 0 0 2 1 1 1 1 2 0 0 0
0 0 0 0 0 0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 2 2 0 1 1 0 2 0 0
0 0 0 0 0 0 0 0 0 2 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3 2
10 9
10 11

Hint

Translated by ChatGPT 5