Гра "Ротація"
У вас є дошка висотою два і шириною W. Вона розділена на 1×1 клітинки. Рядки дошки пронумеровані зверху вниз як 1 і 2, а стовпці — зліва направо від 1 до W. Ми позначаємо клітинку в i-му рядку і j-му стовпці як (i, j). Спочатку на деяких клітинках дошки розміщені шашки, які всі виглядають однаково, тому ми не розрізняємо їх. Вам дозволено виконувати такі операції на дошці:
Квадратне обертання: Виберіть 2×2 квадрат на дошці. Потім перемістіть шашки в цьому квадраті так, щоб вони оберталися на 90 градусів у будь-якому напрямку — за годинниковою стрілкою або проти неї.
Трикутне обертання: Виберіть набір клітинок на дошці, які утворюють трикутник. Ми називаємо набір клітинок трикутником, якщо він утворений шляхом видалення рівно однієї клітинки з 2×2 квадрата. Як і у випадку квадратного обертання, обертайте шашки в обраному трикутнику в будь-якому напрямку — за годинниковою стрілкою або проти неї.
Ваше завдання полягає в тому, щоб перетворити початкове розташування шашок у бажане, виконуючи послідовність обертань. Інформація про початкове та цільове розташування надається як вхідні дані. Для бажаного розташування кожна клітинка (i, j) має одне з наступних значень: i. клітинка (i, j) повинна містити шашку, ii. клітинка (i, j) не повинна містити шашку, або iii. немає обмежень для клітинки (i, j). Обчисліть мінімально необхідну кількість операцій для досягнення відповідності розташування обмеженням і виведіть цю кількість.
Вхідні дані
Вхідні дані мають такий формат:
W
s_11s_12…s_1W
s_21s_22…s_2W
t_11t_12…t_1W
t_21t_22…t_2W
Перша строка вхідних даних містить ціле число W (2 ≤ W ≤ 2000), що визначає ширину дошки. Наступні два рядки містять інформацію про початкове розташування. Якщо клітинка (i, j) містить шашку в початковому розташуванні, s_ij дорівнює o. Інакше s_ij дорівнює .. Потім слідує порожній рядок. Наступні два рядки містять інформацію про бажане розташування. Аналогічно, якщо клітинка (i, j) повинна містити шашку в кінці, t_ij дорівнює o. Якщо клітинка (i, j) не повинна містити шашку в кінці, t_ij дорівнює .. Якщо немає умов для клітинки (i, j), t_ij дорівнює *. Ви можете бути впевнені, що рішення завжди існує.
Вихідні дані
Виведіть мінімально необхідну кількість операцій в одному рядку.