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

Разбор задачи 1493. Подземелье

Определение данных. Так как нас интересует только длина кратчайшего пути, то нет необходимости в массиве from.

const maxn=100; { максимальное значение n и m }
      inf=1000000000; { большое число }
type state=record i,j1,j2:integer; end; 
   { состояние, положение спелеологов - вершина графа }
var
  map:array[1..maxn]of string; { карта лабиринта }
  q:array[1..maxn*maxn*maxn] of state; 
    { очередь обрабатываемых состояний для поиска в ширину }
  q1,q2:integer; 
   { номер первого обрабатываемого элемента очереди
     и номер свободного элемента в конце очереди } 
  d:array[1..maxn,1..maxn,1..maxn]of integer; 
    { массив расстояний для каждого состояния }
  n,i,j,j1,j2,mind,new_i,new_j1,new_j2:integer;

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

begin
  readln(n,m);
  for i := 1 to n do
    readln(map[i]);
  for i := 1 to n do
    for j1 := 1 to m do
      for j2 := 1 to m do
        d[i,j1,j2]:=inf;
  d[1,1,m]:=0; { расстояние для начального состояния равно 0 }
  q[1].i:=1; { помещаем в очередь начальное состояние }
  q[1].j1:=1;
  q[1].j1:=m;
  q1:=1;
  q2:=2;

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

  while q1<q2 do { очередь не пуста }
  begin
    i:=q[q1].i; { извлекаем первое состояние из очереди }
    j1:=q[q2].j1;
    j2:=q[q2].j2;
    inc(q1);
    for new_i:=i-1 to i+1 do { либо оба спелеолога спускаются вместе вниз или вверх }
      if (new_i>=1) and (new_i<=n) and 
         (map[new_i][j1]<>'#') and (map[new_i][j2]<>'#') and
         (d[new_i,j1,j2]>d[i,j1,j2]+1) then
      begin
        d[new_i,j1,j2]:=d[i,j1,j2]+1; { запоминаем найденное расстояние }
        q[q2].i:=new_i; { добавляем состояние в очередь }
        q[q2].j1:=j1;
        q[q2].j2:=j2;
        inc(q2);
      end;
    for new_j1:=j1-1 to j1+1 do { либо спелеологи движутся влево-вправо }
      for new_j2:=j2-1 to j2+1 do { оставаясь на той же высоте }
        if (new_j1>=1) and (new_j1<=m) and 
           (new_j2>=1) and (new_j2<=m) and 
           (map[i][new_j1]<>'#') and (map[i][new_j2]<>'#') and
           (d[i,new_j1,new_j2]>d[i,j1,j2]+1) then
        begin
          d[i,new_j1,new_j2]:=d[i,j1,j2]+1; { запоминаем найденное расстояние }
          q[q2].i:=i; { добавляем состояние в очередь }
          q[q2].j1:=new_j1;
          q[q2].j2:=new_j2;
          inc(q2); 
          { *** }
        end;
  end;

Определение существования пути. В данной задаче конечными состояниями являются все состояния, у которых j1=j2. Находим среди них наименьшее расстояние:

  mind:=inf;
  for i:=1 to n do
    for j1:=1 to m do
      if mind>d[i,j1,j2] then
        mind:=d[i,j1,j1];
  if mind=inf then
    writeln(-1)
  else
    writeln(mind);
end.

Ускорить работу программы можно, добавив печать расстояния и выход из программы, как только конечное состояние будет достигнуто. Код нужно добавить в место, указанное { *** }:

  if new_j1=new_j2 then
  begin
    writeln(d[i,new_j1,new_j2]);
    halt;
  end;

Тогда завершающая часть программы становится проще:

  writeln(-1);
end.