Постановка проблемы: Исследовательская группа хочет создать исследовательский центр в регионе, где они обнаружили редкие элементы. Они хотят сделать его как можно ближе ко всем редким элементам, чтобы они могли снизить общую стоимостьИсследования проводятся там. Дано, что местоположение всех редких элементов связано дорогой. Также считается, что Исследовательский центр может быть построен только на дороге. Команда решила поручить эту задачу кодеру. Если вы чувствуете, что у вас так многопотенциал. Вот задача: - Найти самое короткое из самых длинных расстояний исследовательского центра от заданных местоположений редких элементов. Местоположения даны в форме ячейки матрицы, где 1 представляет дороги, а 0 - нет дорог. Количество редких элементов и их местоположение также было задано (число <= 5), а порядок квадратной матрицы был меньше, чем 20 </p>
Мой подход к решению проблемы состоит в том, чтобы начать BFS (поиск в ширину) с одного из местоположений редких элементов (скажем, X) и заменить значение дороги (отмеченное как 1) на самое короткое значение, чтобы достичь ячейки изэто местоположение X. Аналогичным образом, запустите BFS из всех других мест и добавьте самое короткое значение к существующему значению ячейки. После завершения BFS для всех местоположений отсканируйте матрицу на минимальное значение.
Будет ли работать вышеуказанный подход? Есть ли алгоритм, специально предназначенный для таких задач?