Гра в плитки#6601
Гра в плитки — це змагання для двох учасників, яке відбувається на прямокутній дошці, що складається з рядків і стовпців квадратних клітинок, званих плитками. На початку гри деякі плитки можуть бути зафарбовані чорним кольором, тоді як інші залишаються білими. Гравці по черзі роблять ходи, і той, хто не зможе зробити допустимий хід, програє. Гравець 1 починає гру, вибираючи білу плитку та пишучи на ній число 1. Кожен наступний хід полягає у написанні числа на невикористаній білій плитці, яка прилягає горизонтально або вертикально (але не по діагоналі) до плитки з числом i-1. Зверніть увагу, що Гравець 1 завжди пише непарні числа, а Гравець 2 — парні.
На наступній ілюстрації показано три приклади можливих конфігурацій дошки з R = 3 і C = 4 під час гри. Ліворуч зображено початкову конфігурацію. У центрі показано проміжний стан, де сірим кольором позначено можливі ходи для Гравця 2. Праворуч зображено конфігурацію, коли Гравець 2 виграє, зробивши відповідний хід.
Ваше завдання — створити програму, яка визначить, який гравець виграє, якщо обидва гратимуть оптимально, виходячи з початкової конфігурації дошки.
Кожен тестовий випадок описується кількома рядками. Перший рядок містить два цілі числа і , що вказують на кількість рядків і стовпців дошки (1 \le R, C \le 50). -й з наступних рядків містить рядок B_i з символів, що описує -й рядок початкової дошки. -й символ B_i — це або '.' (крапка), або велика літера 'X', що означає, що плитка в рядку і стовпці відповідно біла або чорна. У кожному тестовому випадку принаймні одна з плиток є білою.
Для кожного тестового випадку виведіть рядок з цілим числом, що представляє номер гравця ( або ), який виграє гру, якщо обидва гратимуть оптимально.
Приклад 1