Проектиране и анализ на компютърни алгоритми. 2005/06

Вероятно сте играли на играта с хиксчета и нули при която печели този който пръв направи линия от 3 негови.

Естествено, тази игра може да се обобщи. Първото нещо по което може да се обобщи е размерът на таблицата. Второто е колко еднакви трябва да се направят в линия за да се спечели. Например игра 7x7 със 7 необходими в линия много трудно завършва с нещо различно от реми, но при по-малко необходими победата си е доста вероятна.

Можем да приемем, че винаги пръв играе 'X'. Вашата задача е да напишете програма която играе тази игра. Вашата програма трябва да чете описание на позиция от стандартния вход и да извежда на стандартния изход описанието на позицията след хода си. Тъй като програмите ви ще бъдат сборени една срещу друга, мола всеки да спазва формата стриктно. Друго ограничение е, че имате 2 секунди на ход.

Описание на позиция:
Всяка позиция започва с един ред с 2 числа - N (3..7) и К (3..N). N показва размера на таблицата върху която се играе, а K необходимият брой еднакви (по ред, стълб или диагонал) за да се спечели.  Следват N реда, всеки от които с по N знака. Всеки знак е 'X', 'О' или '.' (моля забележете че вторият знак не е нула а главно латинско O).

Примерна позиция:
5 4
..X..
.O.O.
.XX..
.....
.....

Вход:
Входните данни са едно описание на позиция във горния формат. Позицията винаги е валидна (достижима от началната), като за да определите кой е на ход може да използвате броя на хиксчета и нули.

Изход:
Изходните данни са едно описание на позицията във горния формат - позицията след като сте играли хода си.

Примерен вход:
3 3
.O.
.XX
...

Примерен изход:
3 3
.O.
OXX
...

Ако спазвате формата и правилата може да се опитаме да направим турнирче между вашите програми.