Зʼєднання

Вказівки

Обчисліть результат партії у 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 не зʼєднав верх і низ.