Перевірка Перевіряючого#6077

Перевірка Перевіряючого

1 секунда

64 мегабайти

Дуже складна

Гра в шашки відбувається на дошці 8 на 8, яка складається з червоних і чорних клітин, що чергуються. Два гравці, Червоний і Білий, починають з $12$ фігур, розставлених у початковій позиції, як показано нижче:

Правила руху та захоплення такі (Примітка: хід вперед означає рух фігури в напрямку до сторони супротивника):

Гравці ходять по черзі.
Фігура може рухатися на одну клітину вперед по діагоналі на будь-яку порожню клітину.
Фігура може перестрибнути через фігуру супротивника, якщо ця фігура знаходиться поруч, а клітина безпосередньо за нею порожня. Після стрибка фігура супротивника знімається з дошки (захоплюється). Якщо після стрибка фігура може зробити ще один стрибок, вона повинна це зробити. Це триває, поки не залишиться можливості для стрибків. Це називається багаторазовим стрибком.
Гравець зобов'язаний зробити стрибок, якщо це можливо. Якщо можливі кілька стрибків, гравець може вибрати будь-який, навіть одинарний стрибок замість багаторазового. (Однак, якщо обрано багаторазовий стрибок, його потрібно завершити.)
Останній рядок на стороні супротивника (рядок, де фігура не може рухатися вперед) є рядком просування гравця. Коли фігура досягає цього рядка, вона стає дамкою і може рухатися та захоплювати назад, а також вперед. Як тільки фігура просувається, її хід закінчується; вона не може почати стрибок або продовжити багаторазовий стрибок після того, як стала дамкою, до наступного ходу.
Фігура може бути перестрибнута не більше одного разу під час ходу (це враховується лише тоді, коли дамка робить стрибок).

Ігри записуються, використовуючи нумерацію клітин, показану вище. Наприклад, простий хід вперед для Білого може бути $22$ - $18$ ; одинарний стрибок для Червоного може бути $14$ - $23$ (захоплення білої фігури на клітині $18$ ); а багаторазовий стрибок для білої дамки може бути $22$ - $31$ - $24$ - $15$ (захоплення червоних фігур на $26$ , $27$ і $19$ ).

Для цієї задачі вам буде надано позицію гри в процесі та набір ходів, які потрібно застосувати, починаючи з цієї позиції, і ви повинні визначити, чи всі ходи є легальними, написавши Розширену Машину Шашок.

Вхідні дані

Вхідні дані складатимуться з кількох екземплярів задачі. Кожен екземпляр починатиметься з двох цілих чисел $r$ і $w$ , що вказують на кількість червоних і білих фігур на дошці (значення $r = w = 0$ r = w = 0 вказує на кінець введення, інакше $1 \leq r, w \leq 12$ 1 \le r, w \le 12). Наступний рядок міститиме $r$ номерів клітин, що вказують на позиції червоних фігур, а наступний рядок міститиме $w$ номерів клітин для білих фігур. Позитивні значення клітин вказуватимуть, що на цій клітині знаходиться звичайна фігура, тоді як негативне значення $- s q$ вказуватиме, що на клітині $s q$ знаходиться просунута фігура. Наступний рядок міститиме одне ціле число $m \geq 1$ m \ge 1, що вказує на кількість ходів, які потрібно зробити, після чого пробіл і один символ (або $R$ , або $W$ ), що вказує, чий хід. Наступні $m$ рядків міститимуть $m$ ходів, використовуючи описану вище нотацію. (Ви можете припустити, що в жодному ході не буде більше $13$ номерів клітин.)

Всі позиції на дошці будуть легальними (наприклад, ніколи не буде двох фігур, що займають одну і ту ж клітину). Ви можете припустити, що фігури, які досягли свого рядка просування, дійсно просунуті; тобто не буде фігур на їхньому рядку просування, які не є дамками.

Вихідні дані

Для кожного екземпляра задачі виведіть або All moves valid, або Move $n$ is invalid, де $n = 1$ n=1 відповідає першому ходу в екземплярі задачі. Якщо є кілька нелегальних ходів, ви повинні вказати лише перший з них.

Приклади

Приклад 1