Построение матрицы смежности. - Pascal

Формулировка задачи:

Условие:

Внутрь квадрата с координатами левого нижнего угла (0,0) и координатами верхнего правого угла (100, 100) поместили N (0<N<31) квадратиков. Необходимо найти кратчайший путь из точки (0,0) в точку (100,100), который бы не пересекал ни одного из этих квадратиков.

Ограничения:

• длина стороны каждого квадратика равна 5; • стороны квадратиков параллельны осям координат; • координаты всех углов квадратиков — целочисленные; • квадратики не имеют общих точек.

Указание.

Строится граф из начальной, конечной точек и вершин квадратиков (ребра не должны пересекать квадраты). Затем ищется кратчайший путь, например, с помощью алгоритма Дейкстры.

Вопрос:

Интересует как построить матрицу смежности из того что дано (где в Matrix[i,j] хранится расстояние от вершины i до вершины j, и наоборот). Есть ли уже готовый алгоритм, или же здравые идеи по тому как это сделать? Связаться можно по icq: 311237113. Заранее благодарен.

Решение задачи: «Построение матрицы смежности.»

Листинг программы

    ZeroPnt:TPoint= (x:0; y:0);
    EndPnt:TPoint= (x:100; y:100);
    TPoint=record x,y:integer; end;
    type TArrs=array[1..30] of Square;
 
    function CrossLine(p1,p2,p3,p4:TPoint):boolean;
    var a,b,c,d,e,f,dt,ds,det,t,s:real;
    begin
         a:=p2.x-p1.x;
         b:=p3.x-p4.x;
         c:=p3.x-p1.x;
         d:=p2.y-p1.y;
         e:=p3.y-p4.y;
         f:=p3.y-p1.y;
         det:=a*e-b*d;
         if det=0 then CrossLine:=false
                  else
                      begin
                           dt:=c*e-f*b;
                           ds:=a*f-c*d;
                           t:=dt/det;
                           s:=ds/det;
                           if (0<s) and (s<1) and
                              (0<t) and (t<1) then CrossLine:=true
                                              else CrossLine:=false;
                      end;
    end;
    
    function Check(sa:TArrs; num:byte; p1,p2:TPoint):boolean;
    var i:integer;
        crossq:boolean;
    begin
         crossq:=false;
         for i:=1 to num do
             begin
                  crossq:=CrossLine(sa[i][1],sa[i][2],p1,p2);
                  if not crossq then crossq:=CrossLine(sa[i][2],sa[i][3],p1,p2)
                                else break;
                  if not crossq then crossq:=CrossLine(sa[i][3],sa[i][4],p1,p2)
                                else break;
                  if not crossq then crossq:=CrossLine(sa[i][1],sa[i][4],p1,p2)
                                else break;
             end;
         Check:=crossq;
    end;
    
    procedure Path(sa:TArrs; num:byte; var graph:GMatrix);
    var i,j,n,m,k:integer;
    begin
         if not Check(sa,num,ZeroPnt,EndPnt) then begin
                                       graph[1,2]:=Dist(ZeroPnt,EndPnt);
                                       graph[2,1]:=Dist(ZeroPnt,EndPnt);
                                      end;
         for i:=1 to num do
             for j:=1 to 4 do
                 begin
                      if not Check(sa,num,ZeroPnt,sa[i][j]) then begin
                                                    graph[1,2+i*j]:=Dist(ZeroPnt,sa[i][j]);
                                                    graph[2+i*j,1]:=Dist(ZeroPnt,sa[i][j]);
                                                   end;
                      if not Check(sa,num,EndPnt,sa[i][j]) then begin
                                                    graph[2,2+i*j]:=Dist(EndPnt,sa[i][j]);
                                                    graph[2+i*j,2]:=Dist(EndPnt,sa[i][j]);
                                                   end;
                 end;
    end;

Объяснение кода листинга программы

Создается переменная ZeroPnt типа TPoint с координатами (0,0).
Создается переменная EndPnt типа TPoint с координатами (100,100).
Создается тип TArrs, который является массивом из 30 элементов типа Square.
Определяется функция CrossLine, которая принимает 4 аргумента типа TPoint и возвращает логическое значение true, если пересечение линий существует, и false в противном случае. Внутри функции вычисляются значения a, b, c, d, e, f, dt, ds, det, t и s. Затем проверяется условие det=0, и если оно выполняется, то функция возвращает false. Если нет, то вычисляются значения dt, ds, t и s, и затем проверяется условие (0<s) и (s<1) и (0<t) и (t<1). Если все условия выполняются, то функция возвращает true.
Определяется функция Check, которая принимает 4 аргумента: sa (массив типа TArrs), num (целое число), p1 (переменная типа TPoint) и p2 (переменная типа TPoint). Функция начинает с инициализации переменной crossq в значение false. Затем она проходит по всем элементам массива sa и вызывает функцию CrossLine для проверки пересечения линий. Если пересечение существует, то значение crossq устанавливается в true. Если пересечение не существует, то функция вызывает функцию CrossLine снова, но уже с другими аргументами. Если пересечение все еще не существует, то значение crossq устанавливается в false. В конце функция возвращает значение crossq.
Определяется процедура Path, которая принимает два аргумента: sa (массив типа TArrs) и num (целое число). Внутри процедуры вызывается функция Check для каждого элемента массива sa. Если пересечение существует, то вычисляются значения graph[1,2] и graph[2,1] для представления расстояния между ZeroPnt и EndPnt. Затем вызывается функция Check для каждого элемента массива sa, но уже с другими аргументами. Если пересечение все еще существует, то вычисляются значения graph[1,2+ij] и graph[2+ij,1] для представления расстояния между ZeroPnt и sa[i][j]. Если пересечение все еще не существует, то вычисляются значения graph[2,2+ij] и graph[2+ij,2] для представления расстояния между EndPnt и sa[i][j].
Код завершается без ошибок и ожидает ввода.