Лабиринты.Графы.Пути

[RegIon]

<-тут скрин
как с этого чуда построить граф с такой спецификой(красные квадраты)

 Написать программу, генерирующую лабиринт (см. выше)     и 
    сохраняющую его как неоринтированный граф, т.е. в виде последовательности рёбер, 
    
    в файл c именем "Labirinth.txt" (без, естественно, кавычек) в следующем формате:
        
        первая строка - Имя Создателя (программы, а не вообще ), группу  и имя файла программы и randseed;
        вторая строка - число рёбер, перечисленных ниже;
        следующие строки - неповторяющиеся пары сообщающихся клеток, (т.е. если есть "00 01", то "01 00"), одна пара в строке. 
        последняя строка - символ "*" 
        
    Например:
        Сидоров Фёдор, гр 866,    FSidLab.pas,  667
  
        50
        00 01
        00 02
        02 12
        ....
         98 99
        *

и ещё,как можно допилить этот код чтоб искал все возможные пути(маркировал по разному):

procedure showpth(x,y,i:integer);//отрисовка одного из путей
var n,k,m:integer;
begin
m:=0;n:=pth[y*10+x];
if(n-1<i)then begin
 pth[y*10+x]:=-2;
if(pth[y*10+x+1]=i-1)then m:=0;
if(pth[y*10+x-1]=i-1)then m:=1;
if(pth[(y+1)*10+x]=i-1)then m:=2;
if(pth[(y-1)*10+x]=i-1)then m:=3;//тут так надо
if(m=0)then showpth(x+1,y,i-1);
if(m=1)then showpth(x-1,y,i-1);
if(m=2)then showpth(x,y+1,i-1);
if(m=3)then showpth(x,y-1,i-1);
end; 
end;

Срочно надо-зачет.

[shybovycha]

Волновой алгоритм. Не уверен, как сделать что-то вроде std::vector / std::queue в паскале, но допустим есть у вас класс, позволяющий добавлять в конец списка элемент и "выталкивать" элемент с начала списка. И допустим есть у вас класс "точка" - ради сохранения координат клетки (строка, столбец). Пускай в матрице M пустая клетка имеет значение 0, а не пустая - свой номер.

Алгоритм следующий:

// прошу прощения за Сишные выражения в некоторых местах =)
stack := [];

for (y := 0 to rows) do
begin
  for (x := 0 to columns) do
  begin
    if (M[y][x] != 0) then //  клетка не пуста
    begin
      stack.push(Point(x, y));
      break;
    end;

    // нашли первую не пустую клетку
    if (stack.size() > 0) then
      break;
end;

// для связи предыдущей и текущей клеток
Point previous := null;

while (stack.size() > 0) do
begin
  Point p := stack.pop(); // достаем из стека координаты первой клетки, от которой будем "плясать"

  // ищем вокруг "пляшущей" клетки все, от которых можем плясать
  if (M[p.y + 1][p.x] != 0) then stack.push(Point(p.x, p.y + 1);
  if (M[p.y - 1][p.x] != 0) then stack.push(Point(p.x, p.y - 1);
  if (M[p.y][p.x + 1] != 0) then stack.push(Point(p.x + 1, p.y);
  if (M[p.y][p.x - 1] != 0) then stack.push(Point(p.x - 1, p.y);

  // случай с перой найденной клеткой
  if (previous != null) then
  begin
    File.WriteLine(M[previous.y][previous.x], ' ', M[p.y][p.x]);
  end;

  previous := p;
end;