Всем доброго времени суток. Прошу помощи при решении задачи. Копаюсь с ней месяц, но не знаю с чего начать. Уже и олимпиада как 2 месяца прошла, а я всё не могу её решить. Мне подсказали что решить можно с помощью ДДП или графов, но мы такое ещё не изучали.
Условие следующее:
Дана матрица размером N×M клеток, где 0 — клетка воды, 1 — клетка суши. Черепашка находится в клетке с координатами A, B. Найти такую клетку C, D на южном побережье так, чтобы время T перемещения было минимальным. Если таких клеток несколько, достаточно указать одну из них. Движется черепашка по соседним клеткам через общие стороны и тратит: 1 час в клетке суши, и 3 часа в клетку с водой (время, затраченное на первую и последнюю клетки маршрута, тоже учитывается). Клетка южного побережья — последняя 1 в каждом столбце матрицы.
Начальные данные:
N, M, A, B — натуральные, не больше 100. В N следующих строках по M цифр 0 или 1 в каждой.
Исходные данные:
В первой строке T — минимальное время движения между клетками. Во втором координаты C, D новой клетки на южном побережье.
Пример для входных данных:
4 5 1 3
0 1 1 0 0
0 1 0 1 0
1 0 0 0 1
1 1 1 1 1
Нужно получить:
7
4 2
Буду очень всем благодарен, кто сможет мне помочь.