Зʼєднання

Вказівки

Обчисліть результат партії у Hex / Polygon.

Абстрактна настільна гра, відома як Hex / Polygon / CON-TAC-TIX, досить проста за правилами, хоч і складна на практиці. Двоє гравців розставляють камені на паралелограмі з шестикутними полями. Перемагає той гравець, який першим зʼєднає свої камені з протилежною стороною. Чотири сторони паралелограма розподілені між двома гравцями (тобто одному гравцеві дістається сторона і сторона, прямо протилежна їй, а іншому - дві інші сторони).

Наша мета - створити програму, яка за простим поданням дошки обчислює переможця (або його відсутність). Зауважте, що не всі ігри мають бути «чесними». (Наприклад, у гравців може бути різна кількість каменів, або дошка гри може мати іншу ширину і висоту.)

Дошки мають такий вигляд:

. O . X .
 . X X O .
  O O O X .
   . X O X O
    X O O O X

«Гравець O» грає згори донизу, «Гравець X» грає зліва направо. У наведеному вище прикладі O утворив зʼєднання зліва направо, але ніхто не переміг, адже O не зʼєднав верх і низ.

Інструкції, специфічні для треку

Можна помітити, що деякі тестові випадки здаються несправедливими. Однак насправді вони можуть бути цілком слушними. Наприклад, юним гравцям або початківцям часто дають додаткові n фігур на фіксованих позиціях на дошці, тож у цілком законній грі кількість фігур може не збігатися.

У будь-якому разі цю вправу цікавить лише визначення переможця гри, яка може мати різноманітні параметри, як-от довжина дошки й додаткові фігури. Її не цікавить жоден інший стан гри, як-от хто куди сходив, коли, чия зараз черга.

Тож не дивуймося цим на позір несправедливим іграм.