Ultimate TTT
Interview Prep 2017
Time Limit: 0.5s, Memory Limit: 128MiB
Някога замисляли ли сте се да напишете изкуствен интелект, който играе морски шах? Оказва се, че броят възможни състояния е толкова малък, че оптималната стратегия е относително очевидна. Тук, обаче, ще разгледаме значително по-интересен вариант на играта.

Във всяко от полетата на стандартната 3 на 3 дъска е нарисувана по-малка дъска:
Empty board example
Двама играчи се редуват да играят в малките дъски, като в случай, че спечелят някоя от тях, все едно са отбелязали знак в голямата:
Game progress example
Целта е да се постигне ред, колона, или диагонал в голямата дъска, като първият играч, който го постигне, е обявен за победител.
End of game example
Малка дъска, в която се е стигнало до равенство, не се зачита за никой от играчите. Ако никой от играчите не успее да спечели три полета от голямата дъска по хоризонтала, вертикала, или диагонал, играта се счита за "равна".

Като цяло и тази игра не е твърде трудна (при оптимална игра винаги се стига до равенство), затова е вкарано ново правило: всеки ход на играч трябва да бъде в тази клетка на голямата дъска, в която предходния играч е играл в малката. Така, ако предходният играч е играл в горна дясна клетка на (която и да е) малка дъска, следващият трябва да играе в някоя от свободните клетки на малката дъска, намираща се в горната дясна клетка на голямата дъска. Ако пък е играл в долна средна клетка на (която и да е) малка дъска, следващият играч трябва да играе някъде из малката дъска, намираща се в средното поле на най-долния ред на голямата дъска.
Empty board example => Empty board example
Първият играч може да избере произволна дъска. Ако след някой ход дъската, в която попада следващият играч, е вече запълнена или спечелена, той също има право да избере произволна (неспечелена) дъска.

От вас се иска да напишете изкуствен интелект, който играе тази игра. Победа ви носи три точки и нула за противника; равенство носи по една точка и за двамата; загуба носи три точки за противника и нула за вас.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа R и C - реда и колоната (индексирани от нула) на голямата дъска, в която трябва да играете. В случай, че можете да играете в произволна дъска, тези числа ще бъдат -1.

На следващите единадесет реда ще бъдат зададени по единадесет символа, описващи текущия стейт на дъската. Полетата, зачеркнати от вас, ще бъдат отбелязани с 'X'. Полетата, зачеркнати от вашия противник, ще бъдат отбелязани с 'O'. Все още свободните полета ще бъдат отбелязани с '.'. Полета, които са свободни, но са върху вече спечелена дъска, ще бъдат "блокирани" с '#'. Ще има хоризонтални ('-'), вертикални ('|'), и смесени ('+') разделители между клетките на голямата дъска. Вижте примерния вход за пояснение.
Изход
На единствен ред на стандартния изход изведете четири цели числа RL, CL, RS, и CS - съответно реда и колоната на клетката в голямата дъска, в която играете, следвани от реда и колоната в малката дъска. Тези числа също трябва да бъдат индексирани от нула. В случай, че R и C не са -1 (тоест клетката от голямата дъска е предопределена), числата RL и CL трябва да съвпадат с тях.
Ограничения
  • -1 ≤ R, C ≤ 2
Примерен Вход Примерен Изход
2 1 O..|.X.|#OX .X.|X.X|OOO X.O|OO.|### ---+---+--- ##X|X##|OO# OOO|XXO|XXX #XX|XOO|### ---+---+--- X.X|.O.|.XO OO.|..X|.O. ...|O.X|.X. 2 1 0 2
На предходния ход противникът ни е сложил 'O' в средната долна клетка на някоя от малките дъски. Това ни кара да сложим в някое от свободните полета на средната долна дъска. Можем да спечелим тази дъска, слагайки в горната дясна клетка (правейки три 'X'-а по вертикала). Така, обаче, ще пратим противника във вече спечелена дъска и той ще може да избере произволна клетка от която и да е от малките дъски.
Линкове
Идеята за играта е взета от тук. Можете да играете един срещу друг тук.

Мрън!