Задача C. Четыре в ряд

Автор:Н. Ведерников, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Игра "четыре в ряд" идёт на прямоугольном клетчатом поле из 7 столбцов и 6 строк. Первоначально все клетки пустые (символ "."). Игроки по очереди ставят на поле свои символы, первый игрок ставит символ "X" (ASCII 88), второй игрок — символ "O" (ASCII 79).

Символ ставится в указанный игроком столбец и "падает" вниз до самой нижней пустой клетки в этом столбце, занимая её. Если все клетки столбца заняты, больше ходов в этот столбец делать нельзя.

Игра заканчивается, когда один из игроков собрал четыре своих символа в ряд по вертикали, горизонтали или диагонали.

Требуется написать программу, которая по указанной позиции игры выведет последовательность допустимых правилами ходов, приводящую к данной позиции, или определит, что это невозможно.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Формат входного файла

Первая строка содержит целое число T — количество тестов. Далее идут описания тестов, на каждый тест 6 строк по 7 символов в каждой — описание позиции. Тесты разделены одиночными пустыми строками.

Формат выходного файла

Выходной файл должен содержать T ответов на тесты.

Каждый ответ состоит из одной строки, содержащей целое число ходов N, за которым следуют N целых чисел pi, разделённых пробелами — последовательность номеров столбцов, в которые ходят игроки. Нечётные i соответствуют ходам первого игрока, чётные — ходам второго игрока. Столбцы пронумерованы начиная с 1.

В случае, если позицию в тесте невозможно получить в игре, выведите для этого теста строку с числом 1.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10
.......
.......
.......
.......
.......
....X..

.......
.......
.......
....X..
....O..
...OX..

.......
.......
.......
....X..
.X..O..
...OX..

.......
.......
.......
....X..
....O..
O..OX..

.......
.......
.......
..X....
....O..
...OX..

.......
.......
.......
....X..
....O..
O..OX..

.......
OO.....
OO.....
OX.....
XX.....
XX.X...

.......
.......
.......
....O..
OOO.OOO
XXXXXXX

.......
.......
.......
.......
OOO.OOO
XXXXXXX

.......
.O.....
OO.....
OX.....
OX.....
XX.XX..
1 5
4 5 5 5 4
-1
-1
-1
-1
-1
-1
13 7 7 6 6 5 5 3 3 2 2 1 1 4
11 1 1 2 1 2 1 2 2 5 2 4

0.043s 0.006s 17