Подразделы

Другие разделы

Дата и время

02/04/2025 17:23:28

Авторизация

Отборочные и районно-городские командные соревнования

A. Семь гномов B. Очередь C. Високосный год D. Гномья нумерация E. Гномий язык F. Сокровища Казад Дума G. Головоломка H. Покраска забора

F. Сокровища Казад Дума

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Гном Тихоня нашел карту, где указано расположение знаменитой сокровищницы Казад Дума. Чтобы попасть в сокровищницу, нужно переставить специальным образом валуны в комнате перед сокровищницей, тогда дверь в нее откроется. Квадратная комната разбита на клетки одинакового размера. В каждой клетке может находиться один валун, который можно перекатить в соседнюю по вертикали или горизонтали свободную клетку. Все валуны одинаковы и взаимозаменяемы. Тихоне известно текущее расположение валунов в комнате и расположение этих валунов для открытия двери. Он хочет переставить валуны как можно быстрее, чтобы успеть попасть в сокровищницу до появления Барлога. Напишите программу, определяющую минимальное число действий для открытия двери (одно действие – это перекатывание валуна в соседнюю свободную клетку).

Первая строка содержит одно целое число

$N$ (

$2\ ≤\ N\ ≤\ 4$ ) – размер стороны комнаты. Далее следует 2*

$N$ строк, содержащих по

$N$ символов '.' и '@'. Первые

$N$ строк содержат текущее расположение валунов, остальные – расположение валунов, при котором дверь в сокровищницу открывается. Символ '.' обозначает пустую клетку, символ '@' – клетку с валуном.

Вывести одно целое число – минимальное число перекатываний.

Пример ввода

2
.@
@.
@.
.@

Пример вывода