школьные олимпиады по программированию.Решение и разбор задач.

{Задача#5.Город-лабиринт.Районная олимпиада-2006}

var a,b:array[1..20,1..20] of char;
s,s1:string;
n,i,j,min:integer;

procedure print;
begin
for i:=1 to n do
begin
for j:=1 to n do
write(a[i,j]);
writeln;
end;
end;

procedure story;
begin
if min>length(s) then
begin
move(s,s1,sizeof(s));
min:=length(s);
end;
end;

procedure p(i,j:integer);
begin
if ((i=n) and (j=n)) and ((a[n,n]='-') or
((s[length(s)]='E') and (a[n,n]='+')))
then story else
begin
if a[i,j]='-' then
begin
if j if j>1 then begin s:=s+'W';a[i,j]:='*';p(i,j-1);end;
end;
if a[i,j]='|' then
begin
if i if i>1 then begin s:=s+'N';a[i,j]:='*';p(i-1,j);end;
end;
if a[i,j]='+' then
begin
if (s[length(s)]='S') and (i if (s[length(s)]='N') and (i>1) then begin s:=s+'N';a[i,j]:='*';p(i-1,j);end;
if (s[length(s)]='E') and (j if (s[length(s)]='W') and (j>1) then begin s:=s+'W';a[i,j]:='*';p(i,j-1);end;
end;
end;
delete(s,length(s),1);
a[i,j]:=b[i,j];
end;

begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
for i:=1 to n do

begin
for j:=1 to n do
read(a[i,j]);
readln;
end;
move(a,b,sizeof(a));
min:=n*n;
s:='';
p(1,1);
if s1='' then write('IMPOSSIBLE') ELSE WRITE(S1+'E');
end .

Анализ и разбор задачи.Знания и умения.

Условие задачи:

Задача 5.Город-лабиринт.

В небольшом городе, имеющем квадратную форму, дорожные службы создали сложную сеть дорог и берут большие штрафы за нарушение правил дорожного движения.Путешественник хочет пересечь этот город, не нарушая правил движения.Для этого он купил на бензоколонке карту города и ввел ее в бортовой компьютер.Путешественник вьезжает в городж с запада по шоссе в северо-западный угол города и должен выехать по шоссе, ведущему на восток, из юго-восточного угла.

Напишите программу, которая должна помочь путешественнику найти кратчайший путь в городе - лабиринте.

Во входном файле в первой строке содержится число n (2<=n<=20)-размеры города.Далее следует n строк по n символов в каждой строке-информация о перекрестках.В городе существует три вида перекрестков.На перекрестке первого типа, обозначаемого во входном файле символом "+"(плюс),запрещены любые повороты, и необходимо продолжить движение в том же направлении.На перекрестке второго типа, обозначаемого символом '|' (вертикальная черта), при движении с запада на восток нужно обязательно повернуть на север или на юг,а придвижении с севера на юг или с юга на север-продолжить движении в том же направлении.На перекрестке третьего типа, обозначаемого символом '-'(минус),при движении с юга на север или с севера на юг нужно обязательно повернуть на запад или восток, а при движении с востока на запад или с запада на восток-продолжить движение втом же направлении.

В выходной файл вывести кратчайший путь от первого перекрестка до выезда из города.Для каждого перекрестка, который встретится на пути путешественниеа, нужно указать направление дальнейшего движения - N (север),S(юг),W(запад), или E(восток).Если проехать через город без нарушения правил невозможно, то вывести сообщение IMPOSSIBLE.

INPUT.TXT
3
-|+
|-|
-++

OUTPUT.TXT
ESWSEEE

Алгоритм

1)Запишем словесно – формульный алгоритм решения этой задачи, копируя многое для нее из алгоритма простого лабиринта

1. ввод размера лабиринта и запись его в массив данных символьного типа char, создадим копию лабиринта для маркировки маршрута, а для записи маршрута объявим переменную s строкового типа :

var a,b:array[1..20,1..20] of char;
s:string;

2. запуск процедуры-рекурсии поиска прохода с точки входа p(1,1) а в ней;
• вначале ставим условие контроля выхода из лабиринта: это если (i=n) and (j=n) – координаты выхода и ((a[n,n]='-') всегда выход или и (a[n,n]='+') and((s[length(s)]='E') если подход с запада и перекресток “-“ если все эти условия выполняются – запись в story все действия с поправкой , что обрабатывается не массив шагов , а строка маршрута S, сам алгоритм такой же:
if (i=n) and (j=n) and ((a[n,n]='-') or ((s[length(s)]='E') and (a[n,n]='+'))) then
story
writeln(s+'E');
procedure story;
begin
if min>length(s) then
begin
move(s,s1,sizeof(s));
min:=length(s);
end;
end;

3. в рекурсии происходит разбор всех типов перекрестков с контролем размеров лабиринта и накопления в строку S маршрута прохода по всем сторонам света, при этом везде ставим метку прохода «*» в последовательности запись – метка – рекурсия, здесь самый сложный перекресток «+».

4. выход из рекурсии , удаление последнего символа в записи маршрута в переменной S ,снятие метки «*» и восстановление типа перекрестка по клону b лабиринта a и возврат в рекурсию для поиска нового маршрута

5. после полного анализа лабиринта и записи кратчайшего маршрута вывод результатов в виде строки кратчайшего маршрута по лабиринту если проезд есть и вывод 'IMPOSSIBLE' если нет.

Знать:

оператор выбора "if <условие> then <оператор>"
циклы с параметром for.., с предусловием while..., с постусловием repeat...
алгоритм простого лабиринта
процедуры и функции обработки строк
обьявление процедуры в Турбо Паскале 7.0

Уметь:

работать с входными и выходными файлами input.txt output.txt

домой