заполнены цифрами от 0 до 9.
// Требуется найти такой путь из клетки (1,1) в клетку (n, m),
// чтобы сумма цифр в клетках, через которые он пролегает, была минимальной;
// из любой клетки ходить можно только вниз или вправо.
Может кто пояснить, насколько быстро будет работать алгоритм для решения такой задачки?
Дело в том, что я её вроде как решил, но для матрицы размером больше чем 13x13 решает довольно долго
довольно долго это сколько?
та конечно можно
14х14 больше 10 секунд
так а тебе надо ускорять?
добваь несколько процесоров и потоков
Для нахождения кратчайшего пути есть алгоритм Дейкстры. Может подойти, если таблицу представить как граф, где ребра, это соседние клетки
еще почитай кроме дейкстры о A* (или просто a star algo)
я правильно понимаю, что прийти в любую клетку модно только из двух соседних (левой и верхней) и больше не из каких?
о это ДП
значит время работы алгоритма равняется количество клеток левее и выше *2
Обсуждают сегодня