Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
{ Бэк-трекинг: Проход по лабиринту                                         }
{ Есть матрица n:m, состоящая из 0 и 1. 1 - это стенка, 0 - проход.        }
{ Надо найти оптимальный проход из точки is,js (нчаало) в точку ie, je     }
{ (конец).                                                                 }
{                                                                          }
{ Входной файл LAB.IN содержит:                                            }
{ 1-я строка - размер поля                                                 }
{ 2-я строка - координаты начальной позиции (row,col)                      }
{ 3-я строка - координаты конечной позиции (row,col)                       }
{ 4-я строка и далее - схему лабиринта из 0 и 1                            }
{ Например:                                                                }
{ 10 10                                                                    }
{ 2 10                                                                     }
{ 1 6                                                                      }
{ 1 1 1 1 1 0 1 1 1 1                                                      }
{ 1 0 0 0 0 0 1 0 1 0                                                      }
{ 1 0 1 1 1 1 1 0 1 0                                                      }
{ 1 0 1 0 1 0 0 0 1 0                                                      }
{ 1 0 1 0 1 0 0 0 1 0                                                      }
{ 0 0 1 0 1 0 0 0 1 0                                                      }
{ 0 0 1 0 1 1 1 1 1 0                                                      }
{ 1 0 0 1 0 1 0 0 0 0                                                      }
{ 1 1 0 0 0 0 0 1 0 0                                                      }
{ 1 1 1 1 1 1 1 1 1 1                                                      }
{                                                                          }
{ Выходной файл LAB.OUT содержит маршрут прохода (i1:j1 ... in:jn):        }
{ 1:10                                                                     }
{ 2:10                                                                     }
{ 3:10                                                                     }
{ ....                                                                     }
{--------------------------------------------------------------------------} 
const LN = 50; LM = 50;
var a:array[1..LN,1..LM] of byte;
    p:array[1..LN*LM,1..2] of byte;
    s:array[1..LN*LM,1..2] of byte;
    n,m,si,sj,ei,ej,index,min:integer;

procedure INIT;
var i,j:integer;
begin
     assign(input,'lab.in'); reset(input);
     assign(output,'lab.out'); rewrite(output);
     readln(n,m);
     readln(si,sj);
     readln(ei,ej);
     for i:=1 to n do begin
         for j:=1 to n-1 do begin
             read(a[i,j]);
         end;
         readln(a[i,n]);
     end;
     index:=0; min:=ln*lm;
end;

procedure Store;
begin
    if (min > index) then begin
        move( p, s, sizeof(p) );
        min:=index;
    end;
end;

procedure DONE;
var i:integer;
begin
    for i:=1 to min do writeln(s[i,1],':',s[i,2]);
end;

procedure FindPath(i,j:integer);
begin
    a[i,j]:=2;
    inc(index);
    p[index,1]:=i; p[index,2]:=j;
    if (i=ei) and (j=ej) then begin
        Store;
    end else begin
        if (i > 1) and (a[i-1,j]=0) then FindPath(i-1,j);
        if (i < n) and (a[i+1,j]=0) then FindPath(i+1,j);
        if (j > 1) and (a[i,j-1]=0) then FindPath(i,j-1);
        if (j < m) and (a[i,j+1]=0) then FindPath(i,j+1);
    end;
    dec(index);
    a[i,j]:=0;
end;

begin
     INIT;
     FindPath(si,sj);
     DONE;
end.


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483