Здравствуйте!
Сразу скажу, что из-за отсутствия свободного времени, не возьмусь за реализацию. Но попробую на словах кое-что описать - мы со школьниками решали задачу "найти кратчайший путь в лабиринте". Как мне кажется, Ваша задача подобна, отличие состоит только в том, что проход разрешался только через сторону клетки, если там нет "стены".
Итак: общий метод - "поиск с возвращением" (backtracking) в сочетании с методом "ветвей и границ", т. к. появляется понятие "рекорда" - способа отсечения бесперспективных ветвей в дереве решений.
Исходные данные: мы выбрали прямоугольный массив целых чисел, где младшие 4 бита (0 или 1) запрещали или разрешали идти на "север", "юг", "запад", "восток" (есть "стена", или нет "стены" в лабиринте), а старшие 4 бита сообщали нам ходили ли мы уже в соответствующие стороны.
Весь путь набирался в стек. Если пришли в тупик, делали шаг назад и пытались исследовать ещё неисследованные пути. И так повторяли, пока не добирались до цели.
Длину найденного пути, конечно же, запоминали - это наш текущий "рекорд".
Далее, принимались искать другие возможные пути по той же схеме, но если есть ещё куда идти, но "рекорд" уже превышен, то нет смысла продолжать - путь уже не кратчайший. Откатываемся на шаг назад и продолжаем исследовать другие пути, следя за "рекордом".
Если нашли какой-то путь короче "рекорда", то у нас есть новый, меньший "рекорд". Соответственно, количество "отсечений" бесперспективных продолжений будет расти, удаляя нас от "полного перебора".
Увы, код нашего старого решения не сохранился.
Тем не менее, надеюсь, вышеописанное сумбурное может оказаться Вам, или Экспертам, которые возьмутся за решение задачи, полезным.

Добрый вечер, Максим Юрьевич! Спасибо.

мы со школьниками решали задачу "найти кратчайший путь в лабиринте".

Исходники остались? Можете выложить?
С уважением

Увы, код нашего старого решения не сохранился.

Это - предпоследнее предложение в моём сообщении

Да..., человек иногда видит то, что рассчитывает увидеть. Спасибо

Код ТР7:
[code h=200] program q183184;
uses
Crt,Graph;
const
n=10;
type
tList=^dList;
dlist=record
x,y:integer;
n,l:tList;
end;
var
a:array[1..n,1..n]of integer;{}
b,c:tlist;
x,y:integer;{}
{функция проверки диапозона}
function R(a:integer):boolean;
begin
R:=(a>0)and(a<=n);
end;
{функция рисования в рекурсивном режиме}
procedure S(b,c:tList);
begin
if b<>c then
begin
S(b,c^.l);
delay(60000);
end;
delay(60000);
FloodFill(10+(c^.y-1)*30+2,10+(c^.x-1)*30+2,15);
delay(60000);
end;
{функция волнового алгоритма}
function W(b:tList):boolean;
var
c,d:integer;
e,f:tlist;
g:boolean;
begin
if b<>nil then
begin
e:=b;
while e^.n<>nil do e:=e^.n;{поиск посленднего элемента}
c:=-1;
repeat
d:=-1;
repeat
if(abs(c)<>abs(d))and{проверка взмоности хода}
R(b^.x+c)and{новое значение в дтапозоне}
R(b^.y+d)and{новое значение в диапозоне}
(a[b^.x+c,b^.y+d]=0)then{свободное поле}
begin
new(f);{новый элемент}
f^.n:=nil;{последний в списке}
f^.l:=b;{ссылка на родителя}
e^.n:=f;{встраиваем в список}
e:=f;{новый последний элемент}
f^.x:=b^.x+c;{координаты элементы}
f^.y:=b^.y+d;{координаты элемента}
end;
inc(d);
until(d>1)or((e^.x=x)and(e^.y=y));{условие выхода}
inc(c);
until(c>1)or((e^.x=x)and(e^.y=y));{условие выхода}
end;
W:=((e^.x<>x)or(e^.y<>y))and(b<>nil);{условие выхода из цикла}
end;
begin{main}
for x:=1 to n do for y:=1 to n do a[x,y]:=0;{сьрос массива}
{}
{препятствия}
a[2,5]:=-1;
a[3,9]:=-1;a[3,10]:=-1;
a[4,1]:=-1;a[4,2]:=-1;a[4,4]:=-1;a[4,9]:=-1;a[4,10]:=-1;
a[5,5]:=-1;
a[6,7]:=-1;
a[7,1]:=-1;a[7,3]:=-1;a[7,4]:=-1;a[7,6]:=-1;a[7,7]:=-1;
a[8,8]:=-1;a[8,9]:=-1;a[8,10]:=-1;
a[9,1]:=-1;a[9,4]:=-1;a[9,6]:=-1;
a[10,1]:=-1;a[10,2]:=-1;
{ввод координаты точки входа}
repeat
repeat
write('Enter xEP:');{x enter point}
readln(x);
until R(x);
repeat
write('Enter yEP:');{y enter point}
readln(y);
until R(y);
until a[x,y]=0;
{формируем начальную точку}
new(b);
a[x,y]:=1;
b^.n:=nil;
b^.l:=nil;
b^.x:=x;
b^.y:=y;
{координаты конечной точки}
repeat
repeat
write('Enter xSP:');{x stop point}
readln(x);
until R(x);
repeat
write('Enter ySP:');{y stop point}
readln(y);
until R(y);
until a[x,y]=0;
{запускаем волновой алгоритм}
c:=b;
while W(c) do c:=c^.n;
{поиск конечной точки}
c:=b;
while((c^.x<>x)or(c^.y<>y))and(c<>nil)do c:=c^.n;
{проверяем уловия}
if(c^.x=x)and(c^.y=y)then
begin{конечная точка найдена}
x:=detect;
{инициализируем графику}
InitGraph(x,y,'');
y:=GraphResult;
if y=0 then{видеорежим инициализирован}
begin{graph mode}
for x:=0 to n do Line(10+x*30,10,10+x*30,10+300);{сетка горизонталь}
for y:=0 to n do Line(10,10+y*30,10+300,10+y*30);{сетка вертикаль}
{рисуем препятствия}
SetFillStyle(1,13);
for x:=1 to n do for y:=1 to n do
if a[x,y]<0 then FloodFill(10+(y-1)*30+2,10+(x-1)*30+2,15);
{рисуеем ходы}
SetFillStyle(1,12);
S(b,c);
repeat until KeyPressed;{ждем клавишу}
CloseGraph;
end{graph mode}
else write('Init Error:',y);{графики нет}
end else write('no path');{нет пути}
{освобождаем память}
repeat
b:=c;
c:=c^.n;
dispose(b)
until c=nil;
ReadKey;
end.{main}[/code]
Волновой алгоритм, реализован только проход через сторону. Вершинами не заморачивался.

Добрый день, Константин Николаевич! Большое спасибо.С уважением

Очень полезная строчка.
Она занимает поле, которое уже не принимает участия в алгоритме.
Без неё, при координатах: ЕР=9,9 и SP=2,2, (к примеру) возникает переполнение кучи (203-Heap overflow error).

Удачи!

Ещё вот это

надо исправить на

Спасибо.

Я в соседней консультации (183185, то же самое задание) дал ответ на эту задачу -- на основе вашей программы. Посмотрите, если интересно.