Справка: Задача конкурса графов: возможно модифицированный Дейкстра или другой альтернативный алгоритм

Question

Я пытаюсь выполнить это конкурсное упражнение о графиках:

XPTO - бесстрашный искатель приключений (немного слишком пугливый для своего блага), который хвастается исследованием каждого уголка вселенной, независимо от того, насколько негостеприимным,На самом деле он не посещает планеты, на которых люди могут легко жить, он предпочитает те, на которых только сумасшедший мог бы пойти по очень веской причине (например, несколько миллионов кредитов).Его последний подвиг пытается выжить в Proxima III.Проблема заключается в том, что Proxima III страдает от штормов сильнокоррозионных кислот, которые разрушают все, в том числе скафандры, которые были специально разработаны, чтобы противостоять коррозии.

Наш бесстрашный исследователь был пойман в прямоугольной области в середине одного из этих штормов,К счастью, у него есть прибор, способный измерить точную концентрацию кислоты в каждом секторе и то, какой урон он нанесет своему скафандру.Теперь ему нужно только выяснить, сможет ли он избежать шторма. Проблема

Проблема состоит в поиске пути эвакуации, который позволит XPTO избежать ядовитого шторма.Вам дается начальная энергия скафандра, размер прямоугольной области и ущерб, который скафандр будет испытывать, стоя в каждом секторе.

Ваша задача - найти выходной сектор, количество необходимых шаговчтобы достичь его, и количество энергии, которое его костюм будет иметь, когда он покинет прямоугольную область.Выбранный путь побега должен быть самым безопасным (т. Е. Тот, где его скафандр будет наименее поврежден).Обратите внимание, что XPTO погибнет, если энергия его костюма достигнет нуля.

Если существует более одного возможного решения, выберите то, которое использует наименьшее количество шагов.Если есть хотя бы два сектора с одинаковым количеством шагов (X1, Y1) и (X2, Y2), выберите первый, если X1

Ограничения 00 ≤ W ≤ 500 ширина прямоугольника
0 ≤ H ≤ 500 высота прямоугольника
0 0 0 ≤ D ≤ 10000 ущерб, нанесенный в каждом секторе

Ввод

Первое приведенное число - это количество тестов.Каждый случай будет состоять из строки с целыми числами E, X и Y. Следующая строка будет содержать целые числа W и H. В следующих строках будет содержаться матрица, содержащая повреждение D, от которого скафандр пострадает в соответствующем секторе.Обратите внимание, что, как это часто бывает у компьютерных фанатов, (1,1) соответствует верхнему левому углу.

Вывод

Если есть решение, на выходе будет оставшаяся энергия, координаты X и Y сектора выхода и число шагов маршрута, которые приведут Родерика к безопасности.В случае, если нет решения, фраза прощай жестокий мир!будет написано.

Пример ввода

3
40 3 3  
7 8  
12 11 12 11  3 12 12  
12 11 11 12  2  1 13  
11 11 12  2 13  2 14  
10 11 13  3  2  1 12 
10 11 13 13 11 12 13 
12 12 11 13 11 13 12  
13 12 12 11 11 11 11  
13 13 10 10 13 11 12  
8 3 4  
7 6 
4  3  3  2  2  3  2  
2  5  2  2  2  3  3  
2  1  2  2  3  2  2  
4  3  3  2  2  4  1  
3  1  4  3  2  3  1  
2  2  3  3  0  3  4  
10 3 4  
7 6  
3  3  1  2  2  1  0 
2  2  2  4  2  2  5  
2  2  1  3  0  2  2  
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1 

Пример вывода

12 5 1 8  
Goodbye cruel world!  
5 1 4 2

В принципе, я думаю, что мы имеемсделать модифицированную Дейкстру, в которой расстояние между узлами является энергией скафандра (и мы должны вычесть ее вместо суммирования, как это обычно бывает с расстояниями), а шаги - это .... шаги, сделанные на пути.Позиция с лучшим биномом (Energy, num_Steps) является нашим «выходом».

Важно: XPTO, очевидно, не может двигаться по диагонали, поэтому мы должны исключить эти случаи.

У меня много идей, но у меня такая проблема с их реализацией ...

Может кто-нибудь помочь мне подумать об этом с каким-нибудь кодом или, по крайней мере, идеями?

Я совершенно не прав?

Answer 1

Поскольку это проблема конкурса, я просто дам небольшую подсказку:

В этом примере весят узлы , а не ребра. Одним из способов преобразования такого графа в обычный вид является замена каждого узла двумя узлами: узлом in и узлом out и направленным ребром от in до out с весом, равным исходному. вес узла. Затем для каждого направленного ребра в исходном графе поместите направленное ребро от узла out одного к узлу in следующего.

Твоя идея звучит хорошо - иди с ней.

Кстати, когда работаете над этими проблемами, попробуйте сами разработать реализацию. Это редко помогает просто увидеть чужую реализацию. Обратитесь за помощью к алгоритму, если вам нужно, но реализуйте его самостоятельно.

Answer 2

Вам не нужно обрабатывать это какими-либо нетрадиционными преобразованиями, как вы сказали (вычитание вместо добавления и т. Д.).

Кратчайший путь от одного узла к другому - это тот, который сводит к минимуму общий урон масти на этом пути, независимо от того, убьет ли вас это путешествие.

Просто найдите кратчайший путь от СТАРТА до ВЫХОДА, суммируя веса ребер, как это принято в обычном подходе Дейкстры, и , затем рассмотрите, возможен ли этот кратчайший путь для данной мощности масти. Если это не так, то Goodbye cruel world!.

Если вы настаиваете на сокращении поиска, как только узнаете, что можете определенно не достигнуть ВЫХОДА, то добавление его после вышеуказанной реализации будет тривиальным: поскольку вы расширяете горизонт поиска в поиске Дейкстры , если даже переход к следующему ближайшему узлу для расширения от вас убивает, то и остальная часть пространства поиска также будет, поэтому вы можете просто прервать и Goodbye cruel world!.

Что касается самого графика, концептуально это то, что вы хотите. Вершины ориентированного графа состоят из всех узлов сетки плюс искусственный узел EXIT.

• Все краевые узлы имеют направленное ребро для выхода; вес этих ребер равен 0
• Все соседние (недиагональные) узлы имеют направленные ребра между ними
  • От узла n1 до n2 вес ребра (т. Е. Ущерб от затрат на проезд от n1 до n2) - это ущерб, нанесенный пребыванием в узле n2 (назовем это damageAt[n2], который вы получаете из D матрицы на входе).

Таким образом, минимальное общее количество урона, которое нужно получить, чтобы перейти от СТАРТА к ВЫХОДУ, составляет damageAt[START] + costOf(shortestPathBetween(START, EXIT)).

В целом, этот подход:

• Требуется только стандартная реализация Dijkstra
• Требуется только очень маленькая модификация, чтобы добавить обрезку
• Требуется только очень простое преобразование из входной сетки в ориентированный граф