ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2004

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Кубик в лабиринте

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
На прямоугольном поле из X на Y квадратных клеток находится куб со стороной, равной длине стороны клетки. За один ход куб может перекатываться через ребро, перемещаясь на соседнюю по вертикали или горизонтали клетку. Между некоторыми клетками могут стоять стенки, которые являются препятствиями. Куб не может перекатываться через препятствия. Куб также не может покидать пределы поля.
Требуется определить минимальное число ходов, необходимых для того, чтобы переместить куб из заданной начальной клетки с координатами A и B в заданную конечную клетку с координатами C и D. При этом в конечном положении верхняя грань должна быть та же, что и в начальном положении.

Исходные данные

В первой строке входа указаны размеры поля X (по горизонтали) и Y (по вертикали), отделенные друг от друга одним или несколькими пробелами. Таким же образом во второй строке указаны A и B, а в третьей – C и D. Далее может следовать информация о стенках. Все числа целые; 2 ≤ X,Y ≤ 10.
После символа ‘v’, расположенного в отдельной строке, перечисляются пары чисел, говорящие о вертикальных стенках. Здесь пара чисел N и M определяет стенку между клетками N,M и N+1,M. Каждая пара чисел расположена в отдельной строке. Пустых строк между парами нет.
После символа ‘h’, стоящего в отдельной строке, перечисляются (таким же образом) пары чисел, говорящие о горизонтальных стенках. Пара чисел N и M определяет стенку между клетками N,M и N,M+1.

Результат

Ваша программа должна записать единственную строку, содержащую минимальное число ходов. При невозможности перемещения в эту строку следует записать текст “No solution”.

Пример

исходные данныерезультат
10 2
1 1
10 1
v
2 1
6 2
h
4 1
11
Источник задачи: II Командный студенческий чемпионат Урала по программированию. Екатеринбург, 3-4 апреля 1998 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1301. Кубик в лабиринте