Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Апрель 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей www.thl.narod.ru


Сегодня мы разберем решение еще одной задачи:

Лабиринт задан в виде матрицы размером n на m. Стенам лабиринта соответствуют единицы, проходам - нули. Определить, можно ли из точки с координатами ( i 1 ,  j 1 ) попасть в точку с координатами ( i 2 ,  j 2 ). Для усложнения задачи можно предложить указать самый короткий путь из заданной точки, причем из всех путей одинаковой длины выбирать путь с наименьшим числом поворотов.

 Вот решение:

Наиболее простым способом решения задач по поиску пути является рекурсивный поиск. Его алгоритм во многом аналогичен рассмотренному в задаче 4.6.
Пусть A(nxm) - матрица, задающая лабиринт (1 - стена, 0 - проход). Напишем процедуру рекурсивного перемещения по лабиринту. Путь прохода будем отмечать цифрами, начиная с 2 (2, 3, 4 и т.д.). Пусть на k-том шаге мы попали на клетку с координатами (i, j). Если это та клетка, путь до которой необходимо было отыскать (с координатами (i2, j2)), то задача решена. Необходимо распечатать матрицу с отмеченным путем и прекратить выполнение программы. Если нет, то необходимо проверить, можно ли перейти на соседнюю клетку (справа, слева, сверху или снизу), и если возможно, то вызвать процедуру перемещения уже с этой клетки. Если перехода на соседнюю клетку нет, то необходимо очистить исходную клетку, чтобы её можно было использовать в других вариантах при поиске пути.
Обозначим move(i,j,k) - процедуру рекурсивного перемещения (i, j - номер клетки, k - номер шага), writematr - процедуру, распечатывающую матрицу A, тогда программа, реализующая предложенный алгоритм, может быть записана следующим образом: 

const n=4; m=5;
type matr=array [1..n,1..m] of integer;
{Матрица, задающая варианты прохода. 1-стена; 0-проход.}
const labir:matr=((1,0,0,0,1),
                  (0,0,1,0,1),
                  (1,0,0,0,0),
                  (0,0,1,0,0));
var a:matr;
    i1,j1,i2,j2,f:byte;
    k:integer;
procedure writematr;
var i,j:byte;
begin
for i:=1 to n do
      begin
         for j:=1 to m do write(a[i,j]:3,' ');
         writeln;
      end
end;
procedure move(i,j:byte; k:integer);
begin
   a[i,j]:=k; k:=k+1;
   if (i=i2)and(j=j2) then begin writematr; f:=1; halt end
   else
   begin
     if (i+1<=n)and(a[i+1,j]=0) then move(i+1,j,k);
     if (j+1<=m)and(a[i,j+1]=0) then move(i,j+1,k);
     if (j-1>0)and(a[i,j-1]=0) then move(i,j-1,k);
     if (i-1>0)and(a[i-1,j]=0) then move(i-1,j,k);
   end;
   a[i,j]:=0; k:=k-1;
end;
begin
  a:=labir;
  writeln('Координаты i1, j1'); readln(i1,j1);
  writeln('Координаты i2, j2'); readln(i2,j2);
  f:=0; k:=2;
  if(a[i1,j1]=1)or(a[i2,j2]=1) then
  writeln ('Неверные координаты')
  else move(i1,j1,k);
  if f=0 then writeln('Прохода нет');
end.

Здесь - labir - матрица-константа 4x5, задающая пример лабиринта, f - переменная, через которую отслеживается, есть ли проход из начальной точки в конечную или нет, процедура halt - стандартная процедура, которая прекращает выполнение программы.
Если взять в качестве начальной точки точку с координатами (4, 1), в качестве конечной - точку с координатами (1, 4), то рассмотренная программа выдаст следующий вариант прохода:

1 0 0 8 1
0 0 1 7 1
1 4 5 6 0
2 3 1 0 0
если что стучитесь в ICQ - 433411487 или Агент@mail.ru
В избранное