Задача с зарубежной компании.
Дается матрица размера n*n. Вы стоите на верхней левой координате, и хотите попасть на правую нижнюю (то есть от (1, 1) в (n, n)).
На матрице стоят числа 0 или 1. За одну операцию можно перейти в соседнюю координату заплатив стоимость, равную значению на позиции.
За какую минимальную стоимость можно попасть в (n, n) от (1, 1)?

Пример:
n = 4
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]
Ответ 0
Решение:

Матрицу можно рассматривать как граф, где каждая ячейка — это вершина, а ребра проводим ко всем соседним вершинам. Вес ребра — это число, которое написано на вершине, куда переходим.

Тогда всего лишь нужно найти кратчайшие расстояния от одной вершины к другой. Подумали об алгоритме Дейкстры?
К сожалению, такое решение не приняли.

Нужно решить за O(n*n), можно ли решить с помощью BFS?
Вообще обычным BFS задачу решить не получится, так как BFS не учитывает вес ребер, а учитывает просто количество ребер, как мы видим минимальное количество ребер не всегда оптимальный путь.

Есть так называемый BFS 0-1, нам всего лишь нужно добавлять в начало очереди те вершины на ребре которых написано 0, и в конец очереди если на ребре стоит 1.
Таким образом BFS в первую очередь будет идти по ребру веса 0, а когда нет возможности то уже по весу 1.


Вопрос на подумать, а можно ли масштабировать такой алгоритм и перестать использовать Дейкстру?

@algoses