- Описание
- Решения
- Разборы
- Кодерун AI β
444. Таблички
Вам даны две таблички, в некоторых ячейках которых записаны положительные целые числа. От вас требуется превратить первую табличку во вторую за минимальное время, пользуясь двумя операциями:
- Переместить число в соседнюю ячейку того же ряда, если эта ячейка не была занята. Такая операция занимает 0 секунд.
- Переместить число в любую пустую ячейку в таблице. Такая операция занимает 1 секунду.
Формат ввода
В первой строке вводятся два числа ( ) — высота и ширина табличек.
Далее вводится описание двух таблиц. Каждая таблица вводится как строк по чисел каждая. Число ( ) равно нулю, если соответствующая ячейка пустая, и равно от 1 до , если иначе. Все ненулевые элементы табличек различные, и равно количеству ненулевых элементов.
Гарантируется, что множество значений элементов в первой и второй табличках совпадает.
Формат вывода
Выведите одно число — минимальное время, нужное на перестановку элементов и превращение первой таблички во вторую. Если это невозможно, выведите -1.
Примечание
Одна из возможных последовательностей операций для первого теста:
- Переместить число 1 в соседнюю ячейку справа за 0 секунд.
- Переместить число 2 в первую ячейку первого ряда за 1 секунду.
- Переместить число 5 в последнюю ячейку второго ряда за 1 секунду.
Ограничения
- Ограничение времени
- 1 с
- Ограничение памяти
- 256 МБ
Примеры
Пример 1
2 4
1 0 2 0
3 5 4 0
2 1 0 0
3 0 4 5
2
Пример 2
3 3
1 2 3
4 5 6
7 8 0
4 2 3
6 5 1
0 7 8
4
Пример 3
2 2
1 2
3 4
2 3
4 1
-1