Как реализовать правильный обход по матрице?

Дело такое, что на учебе было дано задание. Задача кажется не из простых и до решения до сего момента не могу прийти.

Задание: Дана матрица любого размера, каждая ячейка имеет значение, это и будет ее вес. Нам нужно двигаясь с правого верхнего угла, найти кратчайший путь на сумму, которую указывает пользователь. Ходить можно только по вертикали и горизонтали. Повторяющихся ходов не должно быть.

Посмотрел много информации на этот счет, может я ходил куда-то не туда смотреть в интернет, но все сошлось к графам, пересмотрел множество из них и остановился на Jump point search, но подстроить толком под свое решение и не сообразил.

Хотелось бы услышать ваши варианты, а в лучшем случае решение. Всем мир:)