Мурашка Лангтона#787
Мурашка Лангтона, названа на честь математика Крістофера Лангтона, — це клітинний автомат із простими правилами, але цікавими поведінковими властивостями, які вивчають деякі математики. Аналогію між мурашками та автоматом Лангтона проводять так: стан автомата уявляється як "мурашка", а його рух — як подорож цієї мурашки особливим світом.
Світ мурашки — це площина розміром n \times n, де кожна клітинка забарвлена у синій або червоний колір. Число — розмір світу. Кожна клітинка позначається як , де 1 \leq i, j \leq n. Мурашка рухається крок за кроком за такими правилами:
Якщо вона знаходиться на синій клітинці, вона змінює колір клітинки, повертає ліворуч і рухається вперед у напрямку, в якому вона дивиться.
Якщо вона знаходиться на червоній клітинці, вона змінює колір клітинки, повертає праворуч і рухається вперед у напрямку, в якому вона дивиться.
Якщо вона не може зробити хід (мурашка не може залишити межі світу), вона помирає.
Наприклад, якщо мурашка стоїть на червоній клітинці, дивиться на схід, і безпосередньо на південь від неї немає клітинки, мурашка помирає. Якщо ж клітинка на південь є, мурашка рухається туди, повертається на південь, а початкова клітинка стає синьою. Потім мурашка намагається зробити ще один крок і так далі.
Ваше завдання: За (i) конфігурацією світу та (ii) початковою позицією мурашки визначити, чи зможе мурашка дістатися до клітинки . Початковий напрямок мурашки — на північ.
Конфігурацію світу n \times n можна подати як невід'ємне ціле число в бінарному записі з n^2 бітами. Використовуються такі умовності: — синя клітинка, — червона, а бінарне представлення задає клітинки зліва направо, знизу вгору (від найстаршого біта до наймолодшого біта). Наприклад, ( у десятковій системі) задає світ 2 \times 2 з такою конфігурацією:
Аналогічно, ( у десятковій системі) задає світ 3 \times 3 з такою конфігурацією:
У вхідному файлі декілька тестів. Кожний тест — це рядок із чотирьох цілих чисел: , , , , розділених пробілами. Вони означають:
(1 \leq n \leq 16): розмір світу.
(0 \leq c < 2^{n^2}): десяткове представлення n^2-бітної конфігурації.
: початкові координати мурашки (1 \leq x, y \leq n), де клітинка відповідає молодшому біту .
Кінець введення: n = c = x = y = 0.
Для кожного тесту виведіть:
Yes, якщо мурашка досягає клітинки з початкової позиції.
Kaputt!, якщо вона помирає, не досягнувши клітинки .
Гарантується, що для кожного тесту після скінченної кількості кроків мурашка або дістанеться клітинки , або помре раніше.
Приклад 1