forum.boolean.name - Лабиринты.Графы.Пути

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Лабиринты.Графы.Пути (http://forum.boolean.name/showthread.php?t=16490)

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

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

Код:

 Написать программу, генерирующую лабиринт (см. выше)     и 

    сохраняющую его как неоринтированный граф, т.е. в виде последовательности рёбер, 

    

    в файл 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;

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

Ответ: Лабиринты.Графы.Пути

Волновой алгоритм. Не уверен, как сделать что-то вроде 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;