УЧЕБНО - ТРЕНИРОВОЧНЫЕ СБОРЫ К IOI 2003 ДЕНЬ №9 Кубик в лабиринте
Входной файл: input.txt Выходной файл: output.txt Время на тест: 1 секунда Тесты к задаче:Скачать
На прямоугольном поле из X на Y квадратных клеток находится куб со стороной, равной длине стороны клетки. За один ход куб может перекатываться через ребро, перемещаясь на соседнюю по вертикали или горизонтали клетку. Между некоторыми клетками могут стоять стенки, которые являются препятствиями. Куб не может перекатываться через препятствия. Куб также не может покидать пределы поля.
Требуется определить минимальное число ходов, необходимых для того, чтобы переместить куб из заданной начальной клетки с координатами A и B в заданную конечную клетку с координатами C и D. При этом в конечном положении верхняя грань должна быть та же, что и в начальном положении.
Ограничения: Все числа натуральные; 2<=X,Y<=10;
В первой строке входного файла 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".