Первый поиск в ширину с изюминкой

Question

Учитывая двоичную матрицу, где 0 представляют препятствие, а 1 представляют путь, найдите минимальное количество шагов, чтобы добраться от данного источника до места назначения (обход разрешен только в 4 направлениях).Это типичный вопрос BFS.

Источник: (0,0) Пункт назначения: (2,0)

1 1 0 0 1 1 1 1 1

Ответ: 5

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

Если мы перевернем (1,0), мы сможем добраться до пункта назначения с 3 шагами.

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

Об этом спрашивали в одной из популярных компаний .. Любая помощь будет ощутима.

Answer 1

Это решение, о котором я подумал:

Для простоты я буду рассматривать матрицу как график.

Итак, обозначим начальную позицию как s (вершина) ипункт назначения как d (вершина).

Теперь мы будем запускать BFS один раз с источником s и один раз с источником d.

Таким образом, мы имеем для каждой вершины vминимальное расстояние от s до v и минимальное расстояние от v до d (расстояние может быть бесконечностью, например, все вершины со значением 0 в матрице имеют бесконечность расстояния).

Теперь для каждой вершины v со значением 0 в матрице сделайте следующее:

для каждой пары соседей из v (в матрице, не более 4) ГДЕ ЗАМЕЧАЕТ,это означает, что пара вершин a и b отличается от b и a.

Максимум 4! / 2!= 12 пар.

Обозначим пару вершин a и b и вычислим следующее расстояние:

s-> a + 1 + 1 + b-> d (s-> a, b-> d дано, это расстояние для пути s-> a-> v-> b-> d).

Выберите минимум из этих расстояний (максимум 12 из них)и это минимальное расстояние от s до d с перевернутым v.

Теперь вы можете узнать, какое из них перевернуть, а также минимальное расстояние.

Сложность =O (V + E)

РЕДАКТИРОВАТЬ:

Если матрица имеет размер n x n, то V = n ^ 2 и в качестве каждой вершиныимеет не более 4 ребер, тогда E = O(n^2) => O(n ^ 2).