Connect
Interview Prep 2018
Time Limit: 0.5s, Memory Limit: 256MiB
В играта Connect двама души играят на квадратна дъска с размер N на N. Всяка клетка първоначално е бяла, като играчите се редуват да запълват клетките една по една. Първият играч запълва избраните от него клетки със синьо, докато вторият - с червено. На всеки ход играчът, който е на ред, избира някоя от оставащите незапълнени клетки и я запълва със своя цвят. Connect Example

Целта на първият играч (със сините клетки) е да прокара път, свързващ най-лявата колона с най-дясната такава. Целта на вторият играч (с червените клетки) е да прокара път, свързващ най-горния ред с най-долния такъв. Под "път" ще разбираме последователност от съседни клетки. Две клетки считаме за съседни, ако са съседни по хоризонтала, вертикала, или главния диагонал (така всяка клетка има до 6 съседни). Вижте картинката за пример с дъска 7 на 7, в която първият играч е победил.

Играта свършва когато някой от двамата играчи направи желания от него път, или пък се стигне до ситуация, в която вече е невъзможно който и да е от двамата да направи такъв.

Оценяване
Играе се "всеки-срещу-всеки", тоест написаният от вас изкуствен интелект ще играе срещу всеки друг от предадените. Играе се на три дъски: една с размер 3 на 3, една с размер 7 на 7, и една с размер 10 на 10. За да е честно, всяка дъска се играе по два пъти срещу всеки противник – веднъж като първи играч и веднъж като втори играч.

При победа (завършване на вашия път) в даден мач печелите 3 точки. При равенство (никой от играчите не успее да направи път) вие и противникът ви получавате по 1 точка. За загуба, разбира се, не получавате точки.

В случай, че решението ви не завърши за 0.5 секунди в някой от ходовете, или ползва повече от допустимите 256 мегабайта, ви се присъжда служебна загуба и получавате нула точки за съответния мач.
Вход
Всеки ход програмата ви ще бъде изпълнявана отначало. На стандартния вход (конзолата) ще можете да прочетете текущото състояние на дъската. На първия ред ще бъдат зададени две цели числа N и K – съответно размерът на дъската и това дали вие сте първи или втори играч. Следват N реда, всеки с по N числа (0, 1, или 2). 0 обозначава празна клетка. 1 обозначава клетка, запълнена от първия играч. 2 обозначава клетка, запълнена от втория играч.
Изход
На стандартния изход изведете две цели числа R и C – реда и колоната на клетката, която искате да запълните. Клетката (R, C) трябва да е в размерите на дъската (тоест 0 ≤ R, C < N), и да е празна в момента на хода.
Ограничения
  • N ще бъде 3, 7, или 10.
  • K ще бъде 1 или 2.
Примерен Вход Примерен Изход
7 2 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 2 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 2 3 5
Играе се на дъска с размер 7 на 7. Нашият изкуствен интелект играе като втори играч. Решаваме да запълним клетката в средния ред и предпоследната колона (отляво на най-дясната единица).
Мрън!