4. Разработка программного обеспечения.

В директиве Uses я указал использование дополнительного модуля CRT. Он реализует ряд процедур и функций, которые дают возможность управлять режимами работы монитора, получать коды клавиатуры, изменять цвета шрифтов в текстовом режиме работы монитора, воспроизводить звук. В моей программе он используется для процедуры ClrScr, очищающей экран, и для получения кодов клавиш сканирования.

В директиве Label я указал одну метку, которую будет использовать оператор безусловного перехода Goto.

В директиве Const я объявил две константы:

N=20 – максимальное количество строк или столбцов, которое может указать пользователь;

D=50000 – длительность, на которую устанавливается задержка с помощью процедуры Delay.

В директиве Var я указал переменные, которые я использую в своей программе. Я использую три типа данных.

Integer (целочисленный):

x, y - координаты элемента L[y, x] по экрану и матрице;

i, j – количество строк и столбцов в матрице, указанное пользователем;

sx, sy – координаты стартового элемента матрицы;

ly, lx – координаты последнего изменённого элемента;

Array (скалярный, для описания массивов):

L – матрица-лабиринт;

Boolean (логический):

st, fin – параметры проверки нахождения входа и выхода из матрицы.

В моей программе используются три функции. Code – это функция численного типа (integer). Внутри функции объявлена локальная переменная ch символьного типа char. Внутри этой подпрограммы с помощью функции ReadKey переменной ch присваивается значение символа, введённого с клавиатуры. ReadKey используется для получения символа одной из специальных клавиш сканирования – стрелок. После этого функция преобразования ord возвращает порядковый номер, соответствующий нажатому символу, и присваивает его функции code.

Nei – это функция логического типа (boolean).

Рис. 1

В функции по четырём направлениям проверяется (рис. 1), есть ли у активного элемента сосед-ноль, являющийся последним изменённым элементом:

if ((x=lx+1) and (y=ly))

or ((x=lx-1) and (y=ly))

or ((y=ly+1) and (x=lx))

or ((y=ly-1) and (x=lx)) then nei:=True else nei:=False.

Border – это функция численного типа (integer). Внутри функции ей присваивается значение 0, которое далее изменяется на значение от 1 до 4 в зависимости от условий:

1: x = 1;

2: y = 1;

3: x = j;

4: y = i.

В случае если ни одно условие не соблюдено, значение функции остаётся равным нулю.

Программа начинается с очищения экрана. Это требуется во избежание накладывания вывода информации на экране в случае, если программа будет запущена повторно.

Далее используется два последовательных цикла Repeat…Until. В первом пользователь задаёт количество строк, во втором – столбцов. Если введённое количество превышает константу N, то выводится сообщение об ошибке; в противном случае цикл завершается.

Следующим пунктом я поставил метку 1. К ней будет возвращаться программа в случае, если при задании пользователем коридор ушёл в тупик. После метки экран очищается с помощью ClrScr – из-за ненадобности старого лабиринта с тупиком.

Следующий блок программы выводит матрицу на экран. Это делается с помощью двух циклов For, в которых указывается конечное число итераций в виде чисел размерности матрицы – i и j. Первый цикл работает с переменной It. Внутри него создаётся второй цикл и инструкция Writeln без параметров, которая переводит курсор в начало следующей строки экрана. Во время работы второго цикла (работающего с переменной x) на экран выводится единица, а также единица присваивается как значение элемента [y,x] матрицы L.

По окончанию работы циклов пользователь увидит матрицу из i строк и j столбцов, состоящую только из единиц.

Следует отметить, что для лучшей ориентации пользователя во время работы программы следует выводить различные справочные сообщения. Я решил делать это на две строки ниже отображённой матрицы.

Далее помощью инструкции Writeln без параметров позиция курсора перемещается на строку ниже, и с помощью Write выводится сообщение «Перемещайте курсор, чтобы выбрать следующий элемент коридора лабиринта». После вывода сообщения ключевым параметрам st и fin (определяющим начало и конец лабиринта) присваиваются значения False. Также параметрам y и x присваивается значение 1, что делает элемент L [1, 1] активным.

С ледующий блок программы реализует подпункт 2.3. моего алгоритма. Рассматривая его, следует рассказать подробнее о принципе его реализации.

Рис. 2

Для наглядности возьмём пример промежуточного положения лабиринта, изображённого на рис. 2. Положим, что синий ноль – это последний выбранный элемент коридора. По условию лабиринт не содержит тупиков и колец. Следовательно, элементы, прилежащие к коридору с боков, должны быть заблокированы от изменения (на рисунке это красные единицы). Вопросами обозначен возможный путь коридора. После выбора одного из направлений (знак вопроса) остальные два будут заблокированы (опять же, из соображений условий задачи).

Р ис. 3

Положим, выбрано нижнее направление (рис. 3). Как видим, левый элемент заблокирован, и выбрать левое направление нельзя - следовательно, условие соблюдено. Далее, если коридор дойдёт до прошлого выбранного элемента на рис. 1, то он не коснётся его ни сверху, ни снизу, так как соответствующие прилежащие элементы тоже заблокированы. В моей программе их блокировка происходит за счёт присвоения им значения «2»; при этом никаких сообщений об этом на экран не выводится.

Вернёмся к программе. Перед блоком, реализующим вышеупомянутый пункт, блокируются углы матрицы. Программа усложнена так потому, что в этом случае следующим ходом пользователь не войдёт внутрь лабиринта (так как элементы не связываются ходом по диагонали), а лишь расширит вход в лабиринт и уменьшит его возможные размеры. По этой же причине после входа программа автоматически выбирает и следующий элемент – по направлению к центру; но данный блок начнёт работу позже.

Весь пункт 2 объединён в единый цикл Repeat…Until, заканчивающийся по условию fin = True, означающему выход из лабиринта. Внутри цикла используется стандартная процедура GotoXY с параметрами (x, y), и курсор позицию, совпадающую с позицией активного элемента выведенной матрицы. После этого стоит оператор выбора Case, который организует ряд операций в зависимости от значения функции code. Ниже приведены коды специальных клавиш:

75 – левая стрелка;

72 – верхняя стрелка;

77 – правая стрелка;

80 – нижняя стрелка;

13 – клавиша Enter.

В зависимости от кода нажатой стрелки программа проверяет условие на положение курсора у границы и в результате увеличивает или уменьшает параметр y или x. После этого цикл начинается заново, и процедура GotoXY с параметрами x, y передвигает курсор на данную позицию. Таким образом, курсор никогда не выйдет за пределы матрицы, а с передвижением его по экрану программа будет делать активным соответствующий элемент матрицы. Например, пользователь нажимает левую стрелку. В результате работы функции code получается значение 75, и внутри оператора case выполняется соответствующая операция. Проверяется условие x > 1 (активный элемент не находится в первом столбце, следовательно, курсор не расположен у левой границы), и если оно верно, то с помощью процедуры Dec параметр x уменьшается на единицу. Выбор вариантов Case завершается, цикл начинается сначала, и процедура GotoXY передвигает курсор влево.

Если же нажимается клавиша Enter, то проверяется условие L [y, x] = 1 (активный элемент равен единице). После используется условный оператор if-then-else с условием st = False (вход не найден). При первом нажатии enter это действительно так, и определяется элемент входа в лабиринт; в противном случае st = True, и программа пропускает блок поиска входа.

В первом случае программа с помощью функции border проверяет элемент на принадлежность к одной из границ. Если border не равна нулю, то инструкция Write выводит на месте положения курсора ноль, а также соответствующему элементу матрицы L [y, x] присваивается значение 0. После этого координатам входа sy, sx присваиваются значения y, x.

Следующий блок оператора выбора Case в зависимости от конкретного значения border (1, 2, 3, 4) и соответствующей границы автоматически выбирает следующий элемент коридора – по направлению от границы. Как было сказано раньше, эти действия автоматизированы по той причине, чтобы предотвратить прокладку лабиринта по границе, так как пользователь лишь расширит вход в лабиринт и уменьшит его возможные размеры. В любом случае принимаются следующие действия: прилежащие два боковых элемента блокируются (принимают значение «2») и в зависимости от варианта с помощью стандартных процедур Dec или Inc значение x или y изменяется на 1. После окончания вариантов Case запоминаются lx и ly (координаты последнего изменённого элемента), процедура GotoXY с параметрами (x, y) передвигает курсор. Затем активному элементу L[y, x] присваивается значение 0, и также на экран выводится 0 с помощью инструкции Write. После этих операций параметр st получает значение True, что значит, что стартовый элемент найден. Цикл начинается сначала.

Следует отметить, что ввиду особенностей инструкции Write в интегрированной среде Turbo Pascal курсор автоматически перемещается на один символ вправо. Из-за этого процедура GotoXY используется второй раз – после инструкции Write. В будущем я буду опускать эту особенность моей программы.

При повторном прохождении цикла (т.е. в случае второго нажатия enter) условие st = False оказывается неверным, и программа пропускает ветку входа. Идёт проверка функции nei=True. Если это не так (нет ни одного соседа-нуля), то поставить 0 не удастся. В случае успеха 0 записывается в матрицу и на экран. Затем происходит проверка на выход из лабиринта: если border< >0 (элемент находится на границе), то параметру fin присваивается значение True. После этого происходит блокировка неиспользованных ветвей путём проверки двух условий. Первое условие проверяет, что неиспользованный элемент на самом деле является таковым; второе – что он является не частью коридора, а стеной, т.е. равен единице (причём два таких условия задаются для каждого из четырёх направлений). В случае успеха такой элемент блокируется:

if (x<>lx-1) and (L[ly,lx-1]=1) then L[ly,lx-1]:=2;

if (x<>lx+1) and (L[ly,lx+1]=1) then L[ly,lx+1]:=2;

if (y<>ly-1) and (L[ly-1,lx]=1) then L[ly-1,lx]:=2;

if (y<>ly+1) and (L[ly+1,lx]=1) then L[ly+1,lx]:=2;

После блокировки активный элемент становится последним изменённым, поэтому lx, ly принимают значения x, y. Затем следует проверка fin=False (выход пока не найден), и в случае успеха проводится ещё одна – на тупик. Задаются четыре условия для каждого направления, объединённые логическим умножением (and), причём каждое из условий поделено на два подусловия, логически сложенные (or):

if ((L[y+1,x]=2) or (L[y+1,x]=0))

and ((L[y-1,x]=2) or (L[y-1,x]=0))

and ((L[y,x-1]=2) or (L[y,x-1]=0))

and ((L[y,x+1]=2) or (L[y,x+1]=0))

Каждое из четырёх условий верно, если прилежащий к последнему изменённому элемент равен 0 или 2. Если же все условия верны, очевидно, что дальнейший путь невозможен. GotoXY (1, i+2) переводит курсор на i+2 строчки ниже, стандартная процедура ClrEol очищает строку, и инструкция Write выводит сообщение «Тупик. Нажмите любую клавишу, чтобы начать путь сначала». Стандартная функция ReadKey даёт сигнал, что клавиша нажата, и программа переходит к разделу с меткой 1, о котором говорилось ранее. Если же лабиринт не заканчивался тупиком, то альтернативный блок условного оператора if-then-else завершается, а вместе с ним блок оператора выбора case. Цикл завершается при условии, что ввод лабиринта закончен (fin=True).

После цикла процедура GotoXY (1, i+2) переводит курсор на строку сообщений, ClrEol очищает её, и инструкция Write выводит сообщение: «Лабиринт готов к тестированию программой. Нажмите любую клавишу для старта». Переменным x,y присваиваются координаты входа sx, sy, процедура GotoXY переводит курсор в начало лабиринта, параметрам fin, st присваивается значение False, и функция ReadKey будет ожидать нажатия любой клавиши. После нажатия клавиши элемент будет заменён с нуля на восьмёрку, как в матрице, так и на экране, и стандартная процедура Delay обеспечит временную задержку перед тем, как цикл прогона начнётся.

Принцип прогона лабиринта программой в некотором смысле схож с принципом его задания. В начале цикла сохраняются координаты lx, ly. После этого происходит проверка st = False, и в случае успеха оператор выбора if-then-else запускает оператора выбора Case, имеющий четыре действия – увеличение или уменьшение на 1 переменной x или y процедурами Inc и Dec. После параметру st задаётся значение True, и при следующих прохождениях цикла будет выбираться альтернативная ветвь else. Программа использует три условия и четыре действия, записанные последовательно с помощью оператора условия if-then-else. Четвёртое действие производится в случае неверности третьего условия:

if (L[y+1,x]=0) and (ly<>y+1) then Inc(y) else

if (L[y-1,x]=0) and (ly<>y-1) then Dec(y) else

if (L[y,x+1]=0) and (lx<>x+1) then Inc(x) else Dec(x).

Если прилежащий элемент равен нулю и не является последним пройденным элементом лабиринта, то он им становится. После этого блок Case кончается. Процедура GotoXY (x, y) переводит курсор, и элементу L[y,x] присваивается значение 8. Следующим действием Delay производится временная задержка. В конце проверяется функция border, и если элемент находится на границе, переменная fin принимает значение True. Цикл завершается. Процедура GotoXY (1,i+2) переводит курсор на строку сообщений, ClrEol очищает её, и инструкция Write выводит на экран сообщение «нажмите любую клавишу, чтобы выйти из программы». Функция ReadKey ожидает ввода клавиши, и после этого происходит выход из программы.