Langton's Ant
Муравей Лэнгтона, названный в честь математика Кристофера Лэнгтона, представляет собой клеточный автомат с простыми правилами, но интересным поведением, которое изучается математиками. Аналогия между муравьем и клеточным автоматом Лэнгтона заключается в том, что состояние автомата можно представить как "муравей", а его динамику — как путешествие муравья в особом мире.
Мир муравья — это n на n плоскость, где клетки окрашены либо в синий, либо в красный цвет. Число n определяет размер мира. Каждая клетка обозначается парой (i, j), где (1 ≤ i, j ≤ n). Муравей перемещается по миру, следуя следующим правилам:
Если муравей находится на синей клетке, он меняет цвет клетки, поворачивается влево и перемещается на следующую клетку в направлении, в котором он смотрит.
Если муравей находится на красной клетке, он меняет цвет клетки, поворачивается вправо и перемещается на следующую клетку в направлении, в котором он смотрит.
Если движение невозможно (муравей не может выйти за пределы мира), то муравей умирает.
Например, если муравей находится на красной клетке и смотрит на восток, и нет клетки сразу на юг от него, то муравей умирает. Если же есть клетка на юг, муравей перемещается туда, меняет цвет исходной клетки на синий и продолжает движение.
Ваша задача — определить, может ли муравей добраться до клетки (n, n) мира, учитывая (i) конфигурацию мира и (ii) начальную позицию муравья. Предполагается, что начальное направление муравья — север.
Входные данные
Конфигурация мира n на n может быть закодирована натуральным числом в двоичной системе, используя n^2 бит. Приняты следующие соглашения: 0 = синий, 1 = красный, а двоичное представление конфигурации определяет клетки мира слева направо и снизу вверх (от наиболее значимого бита к наименее значимому). Например, двоичное число 0100 (4 в десятичной системе) представляет мир 2 на 2 со следующей конфигурацией:
Соответственно, двоичное число 011010100 (212 в десятичной системе) представляет мир 3 на 3 со следующей конфигурацией:
Входные данные содержат несколько тестовых случаев. Каждый случай состоит из одной строки с четырьмя натуральными числами: n, c, x, y, разделенными пробелами, которые следует интерпретировать как:
n (1 ≤ n ≤ 16): размер мира;
c (0 ≤ c < 2^{(n^2)}): десятичное представление двоичного числа с n^2 битами, описывающего начальную конфигурацию мира;
(x, y): координаты начальной позиции муравья (1 ≤ x, y ≤ n), где позиция (n, n) соответствует наименее значимому биту c.
Конец ввода обозначается строкой, где n = c = x = y = 0.
Выходные данные
Для каждого тестового случая ваше решение должно выводить:
"Yes", если муравей достигает клетки (n, n) из начальной позиции;
"Kaputt!", если муравей умирает, не достигнув клетки (n, n).
Для каждого тестового случая гарантируется, что после конечного числа шагов муравей либо достигает клетки (n, n), либо умирает, не достигнув её.