Входной файл: input.txt Выходной файл: output.txt Время на тест: 15 секунд Автор задачи: А.М. Филинский (г. Гомель) Тесты к задаче:Скачать
Карту местности можно представить в виде целочисленной матрицы Q(N, M). Каждый элемент матрицы описывает состояние соответствующего квадрата местности и может принимать одно из двух значение: 0 – мин нет или 1 – мины есть.
Отряд десантников высаживается в квадрате с координатами (A, B) и должен пройти в квадрат с координатами (C, D). Переход от одного квадрата к другому может происходить только через вертикальную или горизонтальную границу между квадратами. При проходе отряда через заминированный квадрат местности квадрат разминируется, причем на это тратится один час. Длина пути отряда измеряется количеством пройденных квадратов, включая начальный и конечный квадрат.
Требуется составить программу, которая находит для данной карты местности кратчайший путь отряда, при котором на разминирование тратится не более K часов. Если таких путей несколько, то требуется вывести тот, при прохождении которого на разминирование затратится наименьшее количество времени.
Порядок ввода исходных данных
(файл INPUT.TXT):
N M
Q(1, 1) Q(1, 2) … Q(1, M)
Q(2, 1) Q(2, 2) … Q(2, M)
…
Q(N, 1) Q(N, 2) … Q(N, M)
A B
C D
K
Здесь
N – количество строк матрицы; M – количество столбцов матрицы; Q(i, j) – состояние квадрата местности с координатами (i, j); (A, B) – координаты начального квадрата; (C, D) – координаты конечного квадрата; K – максимальное количество часов, которое можно потратить на разминирование. Числа в строке разделяются одним пробелом.
Порядок вывода результатов
(файл OUTPUT.TXT):
Если решение найдено:
Yes
<Hours>
<Length of way>
X1 Y1
X2 Y2
…
X<Length of way> Y<Length of way>
Здесь <Hours> – количество часов, затраченных на разминирование пути отряда; <Length of way> – длина пути отряда (количество пройденных квадратов), включая начальный и конечный квадраты; X
i Yi – координаты i-того квадрата, пройденного отрядом, включая начальный и конечный квадраты.