Е1зе Ведхп

а [±, □ ]: =11; {сделать ход}

1: =п*т ТЬеп {выполнен полный обход} Ведхп ргхпЪ; д: =-Ьгие Епс!

Е1зе Еог к: =1 То 8 Оо гес (х+йх [к] ^ +сЦ [к], Ъ+1); {выбор нового хода}

а[х,:)]: =0; {возврат на один шаг назад} Епс1; Епс1;

Ведхп {заполнение массива} Еог 1: =-1 То п+2 Оо Еог ^: =-1 То т+2 Оо

И (х< 1) Ог (х> п) Ог (□ < 1) Ог (;)> т) ТЪеп а[х,; }]: =-1; Еог 1: =1 То п Оо Еог □: =1 То ш Оо гес (л., ^1); {выбор местоположения первого коня} ^ф

по" Ь д ТЬеп ДОг1" Ье1п (' Невозможно выполнить обход¹); КеасИп; Епс1.

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

Решение. Структуры данных. Из шахмат известно, что ферзь, установленный на поле [/, у], бьет все фигуры, находящиеся на той же самой вертикали у, горизон­тали / и диагоналях, для которых сумма (/ + у) и разность (/ — у) индексов посто­янны. На рисунке показаны значения сумм и разностей индексов для восходящих от 2 до 16 и нисходящих от —7 до 7 диагоналей.

Рассмотрим нашу задачу для доски 4x4. Начинаем просмотр горизонтали 1 и пытаемся найти поле [/, у] для постановки ферзя. Если мы установили ферзя на поле [1, 1], то поля, отмеченные на рисунке «*», считаются занятыми («под боем»). Переходим на вторую горизонталь. Ферзя можно установить на поле [2, 3], тогда

/

у

/

/

/

/

/

/

/

/

\

\

\

\

N

N

\|

\

-7

/

/

/

/

/

/

/

/

10 ^

V

\

\

\

\

\

\

\

-6

/

/

/

/

/

/

/

/

\

\

\

\

\

\

\

\

-5

/

/

/

/

/

/

/

/

\

\

\

\

\

\

\

\

-4

/

/

/

/

/

/

/

/

\

\

\

\

\

\

\

\

-3

/

/

/

/

/

/

/

/

\

\

\

\

\

\

\

\

-2

/

/

/

/

/

/

/

/

\

\

\

\

\

\

\

ч

-1

/ 1

/

/

/ 4

/

/

/

/

к '7

\

\

\

\

\

\

ч

 

поля, отмеченные «#», также выбывают из рассмотрения. Переходим на третью горизонталь, на ней все поля «под боем», поэтому необходимо вернуться на вто­рую горизонталь и попытаться установить на ней ферзя по-другому, рис. б. Следу­ющее поле [2, 4]. Возвращаемся на третью горизонталь, поле [3, 2] свободно. Уста­навливаем ферзя и переходим на четвертую горизонталь. Установить на ней ферзя нельзя. Возвращаемся на третью горизонталь — больше допустимых полей нет, на вторую — на ней также нет и, наконец, на первую.

		*	*	*			*	*	*
	*	*		#		*	*	#
	*	#	*	#		*		*	#
	*		#	*		*	#	@	*

а б в

 

Устанавливаем ферзя на следующее поле [1, 2]. Поля, отмеченные «*», — «под боем», рис. <?, второго ферзя — на поле [2, 4], поля «#» — «под боем», третьего ферзя на поле [3, 1], поля «@» — «под боем». И наконец, четвертого ферзя можно поставить на поле [4, 3].

Итак, логика основной части программы, текст которой приведен ниже, имеет следующий вид:

Ргодгат Ехатр1е__71;

СопзЪ п=8;

к: 1п1: едег=0; {счетчик проверок безопасности полей}. Уаг х: Аггау [1..п] 01: 1п1: едег; {решение}

а: Аггау [1..п] 01: Воо1еап; {вертикаль} ЬгАггау [2..2*п] 01: Воо1еап; {восходящая диагональ (/) } с: Аггау [-п+1..п-1] 01: Воо1еап; {нисходящая диагональ (\) }

Ргосес1иге 1п11:; {начальные значения} - Уаг 1: 1п1: едег;

Вед±п

ГШСкаг (а, 51геО^ (а), Тгие);

*		*	*
*	*	*
	*	#	*
@	*		#

РШСЬаг (Ъ, ЗггеО^ (Ь), Тгие); РШСЬаг (с, 3±т.е05 (с), Тгие);

Епс1;

Ргосейиге' Мсу^е (л.,; ]: 1п" Ьедег); {процедура «фиксируй ход»}

Ведхп

х [ ±]: =□; а [:) ]: =Еа1зе; Ь[1+^]: =Еа1зе; с [х-; ] ]: =Еа1зе; Епс1;

Ргосес1иге Васк_Мс^е (1,; ]: 1п" Ьедег); {процедура «отмена хода»}

Вед1п

а [; ] ]: =" Ьгие; Ъ [х+; ] ]: =" Ьгие; с [х-; ] ]: =" Ьгие; Епс1;

ГипсЫоп Б_Нос1 (х^: 1п" Ьедег): Воо1еап; {функция ^возможен ли ход»} Ведхп

Б_Нос1: =а[Л Апс! Ь ] Апс! с[х-Я Епс1;

Ргосес1иге Ргхп" Ь; {вывод решения}

Уаг х^: 1п" Ьедег;

Ведхп

Еог х: =1 " Ьо п Бо Ведхп

Еог ]: =1 То N Бо.

I ^ ^=x[^] ТЬеп Мг11: е (¹1¹: 2) Е1зе Ш±Ье (' * ': 2) / Югл." Ье1п (х [ 1 ]: 3); Епс1;

ГОгхЪеЬп(к); Епс1;

Ргосес1иге ЗоЗ^е (х: 1п1: едег); {нахождение решения}

Уаг:): 1п1: едег;

Ведхп

I^ 1=п+1 ТЬеп Ведхп 1пс(к); РгхпЪ Епс! Е1зе

Еог То п с! о

I ^ Б_Нос1 (1 ^) ТЬеп Ведхп

1Ук^е(х,: П; Зо]^е(х+1); Васк_Мсууе (х,; ]); Епс1; Епс1;

Ведхп {основная программа}

1пх" Ь; 5о]^е(1); Кеас1Ьп Епс!.

Пример 72. Задача о лабиринте. Прямоугольное клеточное поле ограничено пре­пятствиями. Кроме того, на поле задается произвольная система препятствий, на­чальная клетка, на которой находится Черепашка, и конечная клетка. Найти марш­рут выхода из лабиринта, если он существует, и пронумеровать клетки маршрута в том порядке, в котором проходит их Черепашка. Черепашка может делать шаг на одну клетку в любом из четырех направлений: влево, вправо, вверх, вниз.

Решение. Структуры данных. Клеточное поле размером ТУх М опишем двумер­ным массивом А размерности N + 2, М + 2. При этом будем считать, что у4[/, у] = 0, если клетка [/, у] свободна и не посещалась Черепашкой; > 4 [/, у] = —1, если клетка [/, у] является клеткой, на которой находится пре­пятствие, или находится за пределами лабиринта.

					4
	-1	-1	-1		-1
							— 1
			-1		— 1	— 1
	-1					-1
5.						-1	-и
	-1		— 1	-1

 

Координаты входа — /1, у1, координаты выхода — /2, у2. Они задаются пользо­вателем. Блок задания исходных данных в программе и вывод массива ^доста­точно просты, поэтому остановимся на разборе основной логики. Черепашка, перемещаясь по свободным клеткам 04[/, у] = 0), должна найти клетку выхода (А[й, Д] = 0), запоминая при этом свой путь, и после нахождения отметить свой путь числами, то есть в каждую клетку пути записать номер шага, на котором она проходит эту клетку.

Предположим, что Черепашка находится в клетке а[/, у]. Из этой клетки она может сделать либо шаг на север, либо шаг на восток, либо шаг на запад, либо шаг на юг, если соответствующее направление не закрыто препятствием. Пусть Черепашка осуществляет поиск свободного поля для выполнения хода в следую­щем порядке:

Т — соответствует уменьшению координаты / (Бес(/));

< — — соответствует уменьшению координаты у (Бес(/));

—» — соответствует увеличению координаты у (1пс(/));

1 — соответствует увеличению координаты / (1пс(/)).

Рассмотрим процесс поиска прохода на примере. Пусть в представленном выше лабиринте Черепашка должна найти проход из клетки с координатами /1 = 1, у1 = 3 в клетку с координатами /2 = 6, у2 = 1. Первый шаг делается в начальную клетку, то есть а[ 1, 3]: =1. Из начальной клетки она может сделать шаг только в направле­нии 4 (шс(/)), так как в- направлении 1, 2 произойдет выход за пределы лабиринта, в направлении 3 Черепашка наткнется на препятствие. Следовательно, надо присво­ить а[3, 2] значение 2 (шаг сделан). Далее снова производится анализ направлений хода в том же порядке: направление 1 отбрасывается, так как приводит к возврату, направления 2, 3 тоже отбрасываются, так как там препятствия. Черепашка должна сделать ход вновь в четвертом направлении: а[Ъ, 3]: = 3. Четвертый шаг можно сде­лать в направлении 3 и 4. Пусть Черепашка всегда выбирает первый из всех допусти­мых вариантов, в данном случае 3 (->): а [3, 4]: = 4. Это тупик — с трех сторон клетка с координатами 4, 5 окружена препятствиями. Следовательно, надо вернуться на один шаг назад и попытаться по-другому сделать четвертый шаг. Из предыдущей клетки можно шагнуть еще и в четвертом направлении, то есть а[ 4, 3]: =4. Затем вновь делается шаг в четвертом направлении, единственно возможном (а[5, 3]: =5). И так далее до тех пор, пока Черепашка не доберется до конечной клетки.

Таким образом, при анализе вариантов очередного хода Черепашке необходи­мо проверить, свободна ли рассматриваемая клетка. В этом случае а[/, у] = 0. Ход делать нельзя в клетку, для которой д[/, у] = —1 (выход за границы лабиринта, в клетке препятствие), или а[ /, у] > 0 (ход назад). При выполнении 1-го хода в клетку с координатами /, у надо я[/, у] присвоить значение 1.

Если Черепашка зашла в тупик (в трех направлениях препятствия или границы лабиринта), то она должна попытаться сделать новый вариант прохода. Для этого ей надо вернуться на один шаг назад и проверить оставшиеся варианты из преды­дущей позиции. При этом необходимо «занулить» значение я[/, у].

Выбор варианта хода осуществляется из четырех возможных вариантов. В масси­вах Ь и с, содержащих по 4 элемента, будем хранить приращения к значениям текущих координат, в сумме с которыми они дают возможные координаты нового хода Черепашки:

Ь: Аггау[1..4] 1пЪедег=(-1, О, О, 1);

с: Аггау [ 1.. 4 ] 1п1: едег= (0, -1, 1, 0);

Тогда выбор хода и проверку его возможности можно организовать с помощью цикла

Рог к: =1 То 4 Во

а[х+Ь[к], 1+с[к]] =0 ТЬеп...

Опишем этот процесс в виде рекурсивной процедуры Мп> е(7, у, 1: 1п1е§ег), вход­ными параметрами которой являются значения текущих координат Черепашки и 1 — номер ее очередного шага. Если текущие значения координат совпадут с заданными конечными значениями /2, у2, то необходимо вывести лабиринт с от­меченным проходом Черепашки и закончить работу. Вывод осуществляется проце­дурой РгШ(а: туаггау).

Если прохода из заданной начальной клетки в заданную конечную клетку не существует, то необходимо вывести информацию об этом на экран. В этом случае, после того как Черепашка проверит все возможные способы прохода, и необходи­мый результат не будет получен, значение я[/2, у2] по-прежнему будет равно 0.

Ргодгат Ехатр1е_72;

11зез Сг1:;

Сопз^ п=5; т=6; {размеры поля}

Ь: Аггау[1..4] 1п1: едег= (-1, 0, 0, 1); с: Аггау [ 1.. 4 ] 1п1: едег= (0, -1, 1, 0);

Туре туаггау=Аггау [0..п+1, 0..т+1] 01: 1п1: едег;

Уаг а: туаггау; {исходный лабиринт}

1^, 11, 12, 31^2: 1п1: едег;

Ргосес1иге 1пИ:; {формирование массива а из файла}

Уаг 1, Ь: 1пЪедег; ЪехЪ;

Ведхп

Азз1дп ' с: \1. йаЪ '); Кезе1:;

Рог 1: =0 То п+1 Во Рог То т+1 Бо а[х,; П: =-1;

Рог 1: То п Во Рог з: =1 То т Во Кеас! (а [х, Л); С1озе (I);

Епс1;

Ргосейиге Ргхп.; Ь(а: туаггау); {печать лабиринта}

Уаг 1, 1п1: едег;

Ведхп

Рог х: =1 То п Во Ведхп

Еог □: =1 То ш Во Сазе а[1, 3] -1: ИгИ: е (' * '); О: МгИ: е (' '); Е1зе ЮгИ: е(а[1, з]: 3); Епс1;

ДОг1{: е1п; Епс1; Епс1;

Ргосес1иге 1Ук^е(1, 3, 1: 1п1: едег);

Уаг к: 1п-Ьедег;

Вед1п

1± (1=12) Апс! (3=32) ТЬеп {достигнута конечная клетка}

Ведд.п рг1п1: (а); ехИ: Епс!

Е1зе

Вед1п

Еог к: =1 То 4 Во {выбор направления хода} II а[1+Ь[к], з+с[к]]=0 ТЪеп {шаг сделать можно} Вед±п

а[1+Ь[к], з+с[к]]: =1; {сделать шаг} Ъос! (1+Ь [к], з+с[к], 1 + 1);

а[1+Ь[к], з+с[к]]: =0; {возврат на 1 шаг назад} Епс1; Епс1; Епс1; Вед±п

С1гзсг/ ЮгИ: е1п ('ДАННЫЙ ЛАБИРИНТ: ');

ЮгИ: е1п('_______________ '); 1п11:; Ргл_п1: (а);

Игл_1: е1п (.'ВВЕДИТЕ КООРДИНАТЫ ВХОДА'); КеасИп (И, 3 1); ЮгИ: е1п ('ВВЕДИТЕ КООРДИНАТЫ ВЫХОДА'); КеасИп Ц2, з2); а[11, з1]: =1;

{первый шаг в начальную клетку с координатами И, з1} МоVе (11, 3 1, 2);

II а[12, 3 2]=0 ТЬеп 1йгИ: е1п ('ПРОХОД НЕВОЗМОЖЕН'); КеасИп; Епс!.