Игра на вращение
У вас есть доска высотой 2 и шириной 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; если не должна — .; если нет условий — *. Гарантируется, что решение всегда существует.
Выходные данные
Выведите минимально необходимое количество операций в одной строке.