Uber Вопрос: переключите ячейку от 0 до 1, чтобы получить оптимальный путь

Question

В двоичном лабиринте с 0 и 1, 0 - это действительная ячейка, в которую мы можем перейти, а 1 означает, что ячейка заблокирована.Указанный источник и пункт назначения.Мы должны найти- 1. ЕСЛИ путь существует, если да, найти кратчайший путь.2. Если нам дается возможность переключать одну ячейку с 1 на 0, какую ячейку вы будете переключать, чтобы вы наверняка получили кратчайший путь.

Во второй части, как проверить каждую ячейкубез переключения один за другим, если есть эффективный способ сделать то же самое?

Answer 1

Я думаю, что вместо использования подхода динамического программирования, где вы при любом индексе i сетки берете минимум всех возможных направлений, вы можете использовать жадный подход, когда вы создаете график таким образом, чтобыИндекс i связан со всеми индексами вокруг него (максимально возможно 8) в сетке, которая имеет нулевое значение и использует алгоритм кратчайшего пути между данными двумя узлами.Это также облегчит переключение: вы можете переключать только набор индексов, которые совместно используются источником и местом назначения.