Добрый вечер, вот задача из acmp.ru ( Lines )

У меня возникло 2 вопроса.

1) Хотел бы, что бы помогли разобраться с разбором решения этой задачи, только теоритически. Каким бы образом вы ее решили через графы?

2) Если эту задачу решать через обычный волновой алгоритм, то какие есть методы заполнения матрицы числовыми коэффициентами для нахождения пути?

Например:

.  .  .  .  .
.  0  0  0  .
.  1  .  .  .
.  .  0  0  .
.  .  .  99 .

.   - это свободный путь
0   - стена
1   - нач. точка
99  - конеч. точка

результат заполнения должен быть таким:

4  5  6  7  6
3  0  0  0  5
2  1  2  3  4
3  2  0  0  5
4  3  4  99 6

Может кто-то знает рациональное решение(алгоритм) ?

Спасибо.