A[x,y]:=0;

end;

3. Задача о лабиринте

Классическая задача для изучения темы. Как и предыдущие, не обходится без внимания в любой книге по информатике. Формулировка проста. Дано клеточное поле, часть клеток занята препятствиями. Необходимо попасть из некоторой заданной клетки в другую заданную клетку путем последовательного перемещения по клеткам. Изложение задачи опирается на рисунок произвольного лабиринта и две «прорисовки» с использованием простого перебора и метода «волны». Классический перебор выполняется по правилам, предложенным в 1891 г. Э.Люка в “Математических досугах”:

· в каждой клетке выбирается еще не исследованный путь;

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

Естественными модификациями задачи поиска всех путей выхода из лабиринта являются:

· поиск одного пути;

· поиск одного пути кратчайшей длины методом «волны».

Решение первой задачи.

program Labirint;

const Nmax=...;

dx:array[1..4] of integer=(1,0,-1,0);

dy:array[1..4] of integer=(0,1,0,-1);

type MyArray=array[0..Nmax+1,0..Nmax+1] of integer;

var A:MyArray;

xn,yn,xk,yk,N:integer;

procedure Init;

begin

<Ввод лабиринта, координат начальной и конечной клеток. Границы поля отмечаются как препятствия>;

end;

procedure Print;

....

begin

<вывод матрицы А - метками выделен путь выхода из лабиринта>;

end;

procedure Solve(x,y,k:integer);{k - номер шага, x,y - координаты клетки}

var i:integer;

begin

A[x,y]:=k;