Дистанционная подготовка: применим ли алгоритм Флоида?
применим ли алгоритм Флоида?
by B A - Wednesday, 9 January 2013, 04:44 PM
1329. Кладоискатель
  как решить эту с использованием флоида? или эта задача просто так сюда закатилась? (выложите разбор)
Re: применим ли алгоритм Флоида?
by Александр Кульков - Tuesday, 15 October 2013, 11:50 AM
  Плюсую автору темы. Это явная задача на поиск в ширину, хотя она лежит в категории алгоритм Флойда-Уоршелла. Просьба переместить задачу в соответствующую категорию или же разъяснить ситуацию с тем, как её решать Флойдом...
Re: применим ли алгоритм Флоида?
by Данил Исрафилов - Sunday, 5 July 2015, 01:19 PM
  Да. Он применим.
Re: применим ли алгоритм Флоида?
by Кирилл Медведев - Tuesday, 21 April 2020, 03:50 PM
  Если кому-то это будет актуально:
Задача удачно решается Флойдом.
По заданной карте составляем матрицу смежности размером [N*M][N*M], (0 на главной диагонали, INF если между клетками пути нет, 1 если путь есть).
Запускаем алгоритм Флойда по полученной матрице, после находим минимальное расстояние среди путей от точек входа до сокровища, если все пути равны INF или k = 0 выводим -1.