У Вас не описание алгоритма, а набор слов, не очень аккуратно между собой связанных. Например, "от входа отмечаем знаками '*' путь, двигаясь по пути уменьшения расстояния до выхода". Если прочитать это так, как прочитал я, то это неправильно. А что Вы имели ввиду, непонятно. А неправильно (если читать как я) то, что между двумя клетками с числами, отличающимися на 1, может не быть пути, длиной 1 шаг.
На самом деле, я бы порекомендовал Вам ознакомиться с алгоритмом обхода графа в ширину (BFS). С использованием очереди он будет выглядеть куда изящнее.
Код:
Поместить начальную клетку в очередь.
Пометить начальную клетку числом 0.
Пока очередь не пуста, повторять:
- достать очередную клетку i из очереди.
- всех соседей j клетки i, которые ещё не были в очереди, пометить числом, на единицу большим, чем число в клетке i и затолкать их тоже в очередь.
Ответом будет число в клетке, интерпретируемой как выход.
Это общая идея, кое-что нужно учесть, в зависимости от желаемого результата.
Как вывести при этом маршрут? Нетрудно: когда заталкиваем соседа j клетки i в очередь, отмечаем pi[j]=i, а потом двигаемся по массиву pi от финальной клетки в начальную (в обратном порядке).
А вообще, задача поставлена некорректно.
Цитата:
Дан клетчатый лист бумаги, в котором некоторые клетки закрашены. Требуется найти кратчайший путь из левой верхней клетки в правую нижнюю. Двигаться можно только по вертикали или горизонтали.
В такой постановке кратчайший путь будет таким: сначала идем до упора вправо, а потом до упора вниз. Ведь не сказано, что нельзя ходить по закрашенным клеткам. Они просто закрашены и всё - какой нам дело?
И кстати, должен сказать, что я даже как-то прикалывался на олимпиадах, давая подобные задачи. Все думают, что если что-то закрашено, то это нужно обходить : ) с чего бы...