Лабиринт для кубика
Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к IOI (2002-2003). Кубик в лабиринте
URL первоисточника: http://byoi.narod.ru/
Задачу добавил: elena
Успешно сдано решений: 0
Время на тест - 1 с.
На прямоугольном поле из X x Y (2 <= X, Y <= 10) квадратных клеток находится куб со стороной, равной длине стороны клетки. За один ход куб может перекатываться через ребро, перемещаясь на соседнюю по вертикали или горизонтали клетку. Между некоторыми клетками могут стоять стенки, которые являются препятствиями. Куб не может перекатываться через препятствия. Куб также не может покидать пределы поля.
Требуется определить минимальное число ходов, необходимых для того, чтобы переместить куб из заданной начальной клетки с координатами (A, B) в заданную конечную клетку с координатами (C, D). При этом в конечном положении верхняя грань кубика должна быть та же, что и в начальном положении.
Формат входного файла input.txt:
Первая строка содержит (целые) размеры поля X (по горизонтали) и Y (по вертикали), отделенные друг от друга одним или несколькими пробелами.
Вторая строка содержит (целые) координаты начальной клетки A и B
Третья строка содержит (целые) координаты конечной клетки C и D.
Далее может следовать (а может и не следовать) информация о стенках.
После символа 'v', расположенного в отдельной строке, перечисляются пары чисел, указывающие позиции вертикальных стенок. Здесь пара чисел N и M определяет стенку между клетками N,M и N+1,M. Каждая пара чисел расположена в отдельной строке. Пустых строк между парами нет.
После символа 'h', стоящего в отдельной строке, перечисляются (таким же образом) пары чисел, указывающие позиции горизонтальных стенок. Пара чисел N и M определяет стенку между клетками N,M и N,M+1.
Формат выходного файла output.txt:
Первая строка - единственное целое число - минимальное количество ходов, за которое кубик можно переместить из начальной клетки в конечную. Если это невозможно сделать, выведите NO SOLUTION
Пример входного файла
10 2
1 1
10 1
v
2 1
6 2
h
4 1
Пример выходного файла
11