Ultimate Tic-Tac-Toe
Балканска Олимпиада по Информатика 2015
Time Limit: 0.1s, Memory Limit: 64MiB
Морски шах е игра за двама с изключително прости правила. В началото се започва на празна дъска с три реда и три колони. Първият играч избира една от клетките и я запълва със своя знак ('X'). След това вторият играч избира празна клетка и я запълва със своя знак ('O'). На третия ход отново първият играч ('X') избира празна клетка и т.н. Играчите се редуват и не могат да пропускат ход (а и няма смисъл да го правят). Играта продължава докато някой от играчите сложи три свои знака в един и същи ред, една и съща колона или някой от двата диагонала. Ако дъската се запълни без някой от играчите да е победил (по горните правила), играта се счита за "равен".

Ели и Крис играят на модифицирана версия на играта. Вместо да се играе на стандартната 3х3 дъска, в началото се започва с безкрайна такава. След като първият играч направи своя ход (реално без значение къде), следващият ход може да бъде само на такова поле, което потенциално би могло да бъде на една и съща (3х3) дъска с първия. С други думи вторият ход трябва да е най-много на разстояние 2 по хоризонтала и вертикала от първия ход. Следващите ходове следват сходна логика - играчите винаги трябва да избират полета по такъв начин, че всички досега избрани клетки да могат да бъдат събрани в стандартна дъска 3х3. Както и при обикновения морски шах, играчът, който първи задраска три съседни полета по хоризонтала, вертикала или диагонал, печели. Ако никой от играчите не успее да направи това преди възможните полета да се изчерпят, играта се счита за "равен". Забележете, че колкото повече напредва играта, толкова повече се смалява дъска (полетата, на които може да се играе), докато накрая не стигне стандартните размери 3х3 (стига никой от играчите да не спечели преди това).

Нека разгледаме следния пример:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . O . .
. . X . . . . . . . . . O . . . . X X . . . . . . . . O . . . X X . . . . . . O . . . X X O . . . . . O . . X X O . X . O . . X X O . X . O . O X X O . X . O X O X | O . | . O | O
В примера първият играч ('X') печели, но при оптимална игра на втория играч ('O') това не би било така.

Оптимална игра ще наричаме правенето на такива ходове, с които играчът на ход печели, ако може да се спечели; постига "равен", ако не може да се спечели, но може да се направи равен; или губи ако никое от горните не е възможно. Приемаме, че противникът също играе оптимално. Напишете програма, която по текущо състояние на дъската намира коя клетка би избрал играчът, който е на ход, при оптимална игра.
Вход
На първия ред на стандартния вход ще бъдат дадени две цели числа - N и M - задаващи, съответно, броя оставащи валидни редове и колони от дъската. Следват N реда, всеки с по M символа съответно, описващи текущото състояние на дъската. Гарантирано е, че ще е направен поне един ход и играта няма да е завършила. Дъската ще задава само клетки, все още потенциално участващи в играта. Дъската ще задава всички такива клетки.
Изход
На единствен ред на стандартния изход изведете две цели числа R и C - съответно реда и колоната (индексирани от едно), в която трябва да играе игачът при оптимална игра. Ако има повече от една възможност, можете да отпечатате която и да е от тях.
Ограничения
  • 3 ≤ N, M ≤ 5
  • Всички символи, описващи дъската, са от азбуката {'.', 'X', 'O'}.
Примерен Вход Примерен Изход
3 4 .XX. .... .O.. 1 1
Забележете, че ако играчът, който е на ход ('O'), играе в (1, 4), то 'X' би спечелил (играейки в (2, 3) и поставайки 'O' във "вилица").
Играейки в (1, 1) вече дъската е лимитирана само в колоните 1..3, като така 'X' не може да сложи в (1, 4) и да спечели. Оттам нататък има стратегия, с която 'O' може да постигне "равен".
Мрън!