Входной файл: input.txt Выходной файл: output.txt Тесты к задаче:Скачать Время на тест: 15 секунд
Дано треугольное поле в виде равностороннего треугольника. Оно разбито на
маленькие одинаковые равносторонние треугольники со сторонами, в M раз
меньшими, чем сторона большого треугольника. Вид поля показан на рисунке.
Маленькие треугольники пронумерованы подряд с верхнего ряда вниз по рядам,
начиная с 0. Числами показаны номера треугольников. I-тому треугольнику
приписана пометка Pi.
Имеется также тетраэдр (правильная треугольная пирамида) с ребром, равным
длине стороны маленького треугольника. Тетраэдр установлен на S-том
треугольнике. Все грани тетраэдра пронумерованы следующим образом:
1 грань - основание тетраэдра;
2 грань - правая грань тетраэдра, если смотреть сверху тетраэдра в направлении стороны АВ перпендикулярно ей;
3 грань - левая грань тетраэдра, если смотреть сверху тетраэдра в направлении стороны АВ перпендикулярно ей;
4 грань - оставшаяся грань.
Например, при S=2 жирной линией выделено нижнее ребро третьей грани, а при
S=3 жирной линией выделено нижнее ребро второй грани. J-ая грань тетраэдра
имеет пометку Rj.
Имеется возможность перекатывать тетраэдр через ребро, но при каждом
перекатывании взимается штраф, равный квадрату разности между пометками
совмещаемой грани тетраэдра и треугольника. Требуется перекатить тетраэдр с
треугольника S на D с наименьшим суммарным штрафом (S не равно D).
Входные данные находятся в текстовом файле INPUT.TXT. Первая строка
содержит целые числа S, D и M (M<=90). Каждая из следующих M*M строк
содержит пометку соответствующего треугольника. В строке M*M+2 записаны
пометки граней тетраэдра. Пометки как граней, так и треугольников - целые
неотрицательные числа <= 300. Числа в одной строке разделены пробелами
В выходной файл OUTPUT.TXT должно быть записано одно число - минимально
возможный штраф.