Задача на графы типа лабиринт

[k1r1ch]

Есть такая задача:

8—9.4. «Хитрый офис». Имеется прямоугольное одноэтажное офисное здание размера n x m комнат. При этом между какими-то соседними комнатами стоят глухие стены, а между какими-то имеются двери. Двери из здания наружу проектом не предусмотрены. Проблема заключается в том, что офисный компьютер, управляющий дверями, сошел с ума и, когда человек входит в какой-то офис, компьютер закрывает и блокирует дверь, через которую человек вошел, и дверь по левую сторону от вошедшего (если эта дверь в комнате существует). Иными словами, офис можно проходить или прямо, или поворачивая направо. Когда человек выходит из комнаты, блокировки со всех ранее заблокированных дверей снимаются. Клерк хочет пройти из своего офиса в офис начальника. Сможет ли он это сделать? Если сможет, через какое минимальное количество офисов (не считая своего офиса и офиса начальника) ему необходимо будет пройти? В начале все двери разблокированы. Также из своего офиса клерк может выйти в любую имеющуюся дверь.

Формат ввода: В первой строке входного файла содержатся два натуральных числа n и m (1 <= n,m <= 20) — размеры здания. Далее графическим образом задается план здания: 2n + 1 строк по 2m + 1 символов в каждой. На плане символами «-» (дефис), «|» (вертикальная черта) и «+» (плюс) обозначены стены, символами « . » (точка) — двери, «*» (звездочка) — офисы, «С» («С» латинское заглавное) — офис клерка, «В» («В» латинское заглавное) — офис начальника. Четыре символа, смежные с символами офисов, всегда либо стены, либо двери (см. пример).

Формат вывода: В первой строке выходного файла содержится либо строка NO, если клерк пройти к начальнику не сможет, либо YES, если сможет. В последнем случае вторая строка должна содержать целое число — количество офисов, через которые пройдет клерк на своем пути.

Пример 1:
input.txt
1 2
+-+-+
|C|B|
+-+-+

output.txt
NO

Пример 2:
input.txt
3 3
+-+-+-+
|B.*.*|
+.+.+.+
|*|C|*|
+.+-+.+
|*.*.*|
+-+-+-+

output.txt
YES
7

Я думаю, что алгоритм такой:
- Составить граф на основе входа
- Выбрать наименьшую дугу
Вот то, что я сделал за 3 дня копания :

program Obl1x8x4;
uses CRT;
type
  TPoint = record
    X: integer;
    Y: integer;
  end;
const
  WALL = 0;
  OFFICE = 1;
  DOOR = 2;
  CLERC = 3;
  BOSS = 4;
var
  Inp, Outp: Text;
  Width, Height, NumOfDoors, i, j, N: integer;
  Room: array [1..100, 1..100] of integer;
  Line: array [1..100] of TPoint;
  Temp: char;

procedure AddLine;
begin
  Line[N].X := j;
  Line[N].Y := i;
  Line[N+1].X := j + 2;
  Line[N+1].Y := i;
  Inc(N, 2);
end;

begin
  ClrScr;
  NumOfDoors := 0;
  N := 1;
  Assign(Inp, 'Input.txt');
  Reset(Inp);
  Readln(Inp, Height, Width);
  for i := 1 to Height * 2 + 1 do
    begin
      for j := 1 to Width * 2 + 1 do
        begin
          Read(Inp, Temp);
          case Temp of
            '+', '-', '|': Room[j, i] := WALL;
            '*': Room[j, i] := OFFICE;
            '.':
              begin
                Room[j, i] := DOOR;
                Inc(NumOfDoors);
              end;
            'C': Room[j, i] := CLERC;
            'B': Room[j, i] := BOSS;
          end;
        end;
      Readln(Inp);
    end;
  for i := 1 to NumOfDoors do
    for j := 1 to NumOfDoors do
      if Room[j, i] = DOOR then
        begin
          if Room[j+2, i] = DOOR then AddLine;
          if Room[j+1, i-1] = DOOR then AddLine;
        {пока все)}

  repeat until keypressed;
end.

То есть сначала заполняю массив, анализируя вход, а потом пытаюсь составить граф, но пока че-то не очень . Задачу на графы решаю в первый раз, помогите советом или кодом, если не затруднит.

[LeBron]

Решение - обход в ширину с начальной клетки до тех пор, пока не посетим искомую клетку.
Если это ваша первая задача на графы, советую начинать с чего-нибудь еще более простого в плане алгоритма (например, простой BFS без "левых ограничений"), и значительно более простого в плане кодинга (потренируйтесь на 0-1 матрицах). Когда натренируетесь на проостых задачах, с вот такими проблем не будет - так как они стандартные и ничего, кроме набитой руки, сдесь не требуется.
По поводу BFS - для каждого элемента стека так же храним, откуда мы пришли - тогда даже не надо ничего блокировать/деблокировать, просто проверяем 2 возможных ветвления.

[k1r1ch]

BFS - это и есть поиск в ширину?
И еще, можно примеры простых задач?

[LeBron]

Breadth-first search, он самый. В википедии и на сайтах алгормитмики есть и реализация, и объяснение, и доказательство. 2 самые простые задачи на эту тему:
1. Дана матрица из 0 и 1. Даны начальная координата и конечная координата (х и у двух клеток). Найти самый короткий путь между ними (путь существует, "двигаться" можно с клетки с нолем в любую соседнюю клетку с нолем).
2. Почти то же самое, но цель - найти выход из лабиринта. Дана координата клетки, из которой можна покинуть лабиринт и начальная координата "жертвы лабиринта". Найти длину кратчайшего пути к выходу.
Таких задач много на АСМ-сайтах для новичков, можете потренироватся там. Сразу будете видеть, правильно ли решаете, а в форумах/обсуждениях сможете найти помощь относительно некоторых частых вопросов и проблем.