4. Поиск в ширину

Разбор задачи 54. Lines

Определение данных

const maxn=250; { максимальное значение n }
      inf=1000000; { большое число }
type state=record i,j:integer; end; 
   { состояние, в котором находится шарик - вершина графа }
var
  map:array[1..maxn]of string; { карта лабиринта }
  q:array[1..maxn*maxn] of state; 
    { очередь обрабатываемых состояний для поиска в ширину }
  q1,q2:integer; 
   { номер первого обрабатываемого элемента очереди
     и номер свободного элемента в конце очереди } 
  d:array[1..maxn,1..maxn]of integer; 
    { массив расстояний для каждого состояния }
  start_i,start_j,end_i,end_j:integer; 
    { начальное и конечное состояние шарика }
  from:array[1..maxn,1..maxn]of state;
    { для каждого состояния - из какого состояния было достигнуто это состояние }
  di:array[1..4] of integer=(0,0,-1,1); { массив возможных переходов }
  dj:array[1..4] of integer=(1,-1,0,0); { между состояниями }
  n,i,j,k,new_i,new_j:integer;

Ввод и инициализация

begin
  readln(n);
  for i := 1 to n do
  begin
    readln(map[i]);
    for j := 1 to n do
      if (map[i][j]='X') then
      begin
        end_i:=i;
        end_j:=j;
      end
      else if (map[i][j])='@' then
      begin
        start_i:=i;
        start_j:=j;
      end;
  end;
  for i := 1 to n do
    for j := 1 to n do
      d[i,j]:=inf;
  d[start_i,start_j]:=0; { расстояние для начального состояния равно 0 }
  q[1].i:=start_i; { помещаем в очередь начальное состояние }
  q[1].j:=start_j;
  q1:=1;
  q2:=2;

Поиск в ширину, основной цикл

  while q1<q2 do { очередь не пуста }
  begin
    i:=q[q1].i; { извлекаем первое состояние из очереди }
    j:=q[q2].j;
    inc(q1);
    for  k:= 1 to 4 do 
    begin
      new_i:=i+di[k]; { рассматриваем все возможные переходы }
      new_j:=j+dj[k];
      if (new_i>=1) and (new_i<=n) and 
         (new_j>=1) and (new_j<=n) and
         (map[new_i][new_j]<>'O') and { переход допустим }
         (d[i,j]+1<d[new_i,new_j]) then { и еще тут не были }
      begin
        d[new_i,new_j]:=d[i,j]+1; { запоминаем найденное расстояние }
        q[q2].i:=new_i; { добавляем состояние в очередь }
        q[q2].j:=new_j;
        inc(q2);
        from[new_i,new_j].i:=i; { запоминаем, откуда пришли }
        from[new_i,new_j].j:=j;
      end;
    end;
  end;

Определение существования пути и обратная трассировка для вывода найденного пути

  if (d[end_i,end_j]=inf) then { осталось большое число }
    writeln('N') { путь в конечное состояние не найден }
  else
  begin
    writeln('Y'); { путь найден }
    i:=end_i; { восстанавливаем кратчайший путь по массиву from }
    j:=end_j;
    while d[i,j]>0 do
    begin
      map[i][j]:='+';
      new_i:=from[i,j].i; { если сразу присваивать переменным i,j }
      new_j:=from[i,j].j; { то в этом операторе обратимся к неправильной ячейке }
      i:=new_i;
      j:=new_j;
    end;
    for i := 1 to n do { вывод карты с найденным путем }
       writeln(map[i]); 
  end;
end.