Задан лабиринт, по которому ползает змейка. Найти минимальный путь от входа к выходу, при условии, что змейка может одновременно преломляться N=2 раз. Что необходимо от программы:
1. есть змейка, 5-10 элементов. В каждый момент времени допустимое количество изгибов N=2. Есть лабиринт, 10 на 10. Есть координаты входа и выхода (задаются пользователем)
2. найти оптимальный путь от входа к выходу с учетом допустимого количества изгибов, графически изобразить каждое промежуточное положение змеи на пути от входа к выходу
3. если невозможно выполнить п.2, показать начальное положение змеи на входе и конечное у выхода, с выводом на экран всех координат пути, по которому прошла змея, координаты входа и выхода.
Программу написать на Visual Prolog 5.2
Исходный код программы для Visual Prolog 5.2:
%Dannaya programma napisana dlya polya 5x5, dlya polya 10x10 nado ispravit vse
%vstrechayushiesya v programme cifri 6 na 11. Ne ochen sovetuyu eto delat, a takze
%sovetuyu vvodit labirint s kak mozno bolshim kolichestvom stenok, poskolku esli slihkom
%mnogo vozmoznuh putei dlya zmeiki, to mozet ne hvatit razmerov steka pamayti
domains
labfield=l(char,integer,integer) %kazdoe pole hranitsya v vide l(Znak, Koordinata Y, Koordinata X).
labirint=labfield* %labirint - eto spisok polei
snakefield=s(integer,integer). %pole,zanimaemoe zmeikoi hranitsya kak s(Koordinata Y, Koordinata X).
snake=snakefield* %zmeika - spisok sootvetstvuyushih polei
way=snake* %put, proidennii zmeikoi - spisok polozenii zmeiki
ways=way* %puti - spisok putei
predicates
readlab(labirint,integer).
nondeterm printlab(labirint,integer,integer,snake).
string_to_list(string,integer,integer,labirint).
append(labirint,labirint,labirint).
append(ways,ways,ways).
nondeterm member(labfield,labirint).
nondeterm member(snakefield,snake).
nondeterm member(snake,way).
gensnake(integer,integer,integer,snake).
nondeterm findway(labirint,integer).
nondeterm nextposition(labirint,way,way).
nondeterm nextfield(integer,integer,integer,integer).
nondeterm step(labirint,snake,snake).
nondeterm search(labirint,ways).
dellast(snake,snake).
nondeterm printway(labirint,way).
nondeterm empty(labirint,integer,integer).
countbends(snake,integer).
clauses
%predikat, proveryayushii yavlyaetsya li pervii parametr elementom spiska - vtorogo parametra
member(H,[H|_]). %esli on sovpadaet s golovoi, to da
member(H,[_|Tail]):-member(H,Tail). %esli yavlyaetsya elementov hvosta, to da
%predicat, obiedinyayushii dva spiska
append([],B,B). %esli pervii spisok pustoi, to rezultat - vtotoi spisok
append([H|Tail],B,[H|NewTail]):-append(Tail,B,NewTail). %esli ne pustoi, to rekursivno obiedinyaem hvost i vtoroi spisok
%predicat, perevodyashii schitannuyu stroku v spisok polei
string_to_list("",_,_,[]):-!.%esli stroka pusta, to i spisok pust
%esli ne pusta, to berem pervii simvol stroki, zapisivaem v nuznom formate, uvelichivaem schetchik,
%harakterizuyushii X koordinatu polya na 1 i rekursivno perevodim ostavshuyusya chast stroki
string_to_list(S,I,J,[l(C,I,J)|Tail]):-frontchar(S,C,STail),J1=J+1,string_to_list(STail,I,J1,Tail).
%schitivanie vsego labirinta
readlab([],6):-!.%esli doshli do schitivaniya 6i stroki, to otvet pustoi spisok
%inache shitivaem stroku pod nomerom I, perevodim ee v spisok, uvelichivaem nomer stroki na 1,
%rekursivno schitivaem ostavshuyusya chast labirinta, i slivaem vmeste poluchivshiesya spiski polei
readlab(L,I):-readln(S),string_to_list(S,I,1,H),I1=I+1,readlab(Tail,I1),append(H,Tail,L).
%predikat, vivodyashii labirint, uchitivaya polozenie zmeiki
printlab(_,6,_,_):-!.%esli nomer stroki raven 6, to ostanavlivaemsya
printlab(Lab,I,6,Snake):-!,nl,I1=I+1,printlab(Lab,I1,1,Snake).%esli nomer simvola v stroke raven 6,
%to uvelichivaem nomer stroki i vivodim ostavshuyusya chast labirinta
%esli tekushee pole yavlyaetsya takze polem, zanimaemim zmeikoi, to vivodim * i ostavshuyusya chast labirinta
printlab(Lab,I,J,Snake):-member(s(I,J),Snake),!,write('*'),J1=J+1,printlab(Lab,I,J1,Snake).
%esli ze ne zanyato zmeikoi, to vivodim to, chto hranitsya s spiske polei labirinta
printlab(Lab,I,J,Snake):-member(l(C,I,J),Lab),write(C),J1=J+1,printlab(Lab,I,J1,Snake).
%predikat, generyashii nachalnoe polozenie zmeiki zadannoi dlini. Schitaem, chto iznachalno ona zanimaet odno pole
gensnake(_,_,0,[]):-!. %esli dlina ravna 0, to spisok pust
gensnake(X,Y,N,[s(X,Y)|Tail]):-N1=N-1,gensnake(X,Y,N1,Tail). %inache generim pole s zadannimi koordinatami i rekursivno generim hvost
%predicat poiska puti. Nahodit koordinati vhoda v labirint, generit zmeiku na etom pole i zapuskaet predicat poiska
%Poskolku nado naiti kratchaishii put, to ispolzuetsya posik v shirinu.
findway(Lab,N):-member(l('I',X,Y),Lab),gensnake(X,Y,N,Snake),search(Lab,[[Snake]]).
%predicat, vozvrashayushii koordinati polya, na kotoroe teoreticheski mozet peremistitsya zneika s zadannogo polya
nextfield(X,Y,X,Y1):-Y1=Y+1;Y1=Y-1.
nextfield(X,Y,X1,Y):-X1=X+1;X1=X-1.
%predicat dlya udaleniya poslednego elementa spiska
dellast([_],[]):-!.
dellast([H|Tail],[H|NewTail]):-dellast(Tail,NewTail).
%predicat, proveryayushii yavlyaetsya li zadannoe pole pustim
empty(Lab,A,B):-member(l('_',A,B),Lab);member(l('O',A,B),Lab).
%predicat, schitiyushii kolichestvo izgibov v zmeike
countbends([_,_],0):-!.%esli dlina menshe 3, to otvet 0
%esli pervaya koordinata pervih treh sovpadaet, to oni ne obrazutyu igib, prosto rekursivno smotrim dalshe
countbends([s(X,_),s(X,Y2),s(X,Y3)|Tail],N):-!,countbends([s(X,Y2),s(X,Y3)|Tail],N).
%analogichno so vtoroi koordinatoi
countbends([s(_,Y),s(X2,Y),s(X3,Y)|Tail],N):-!,countbends([s(X2,Y),s(X3,Y)|Tail],N).
%syuda iz-za otsecheniya popadaem tolko esli ne vipolneno ni odno iz pervih treh pravil,
%znachit izgib suchestvuet i kolichestvo izgobov, poluchennih posle rekursivnogo vizova, neobhodimo uvelichet na 1
countbends([_,s(X2,Y2),s(X3,Y3)|Tail],N1):-countbends([s(X2,Y2),s(X3,Y3)|Tail],N),N1=N+1.
%predicat, generyashii polozenie zmeiki posle togo, kak ona sdelaet odin dopustimii shag
step(Lab,[s(X,Y)|Tail],[s(A,B),s(X,Y)|NewTail]):-
nextfield(X,Y,A,B),empty(Lab,A,B),%nahodim potencialnoe sleduyushee pole, proveryaem ego na pustotu
dellast(Tail,NewTail),countbends([s(A,B),s(X,Y)|NewTail],N),N<3. %udalyaem poslednii element zmeiki,
%schitaem kolichestvo izgibov, i proveryaem, chtobi ono bilo menshe 3
%predicat, generyashii dlya zadannogo puti zmeiki, put, kotorii ona mozet proiti s uchetom sleduyushego shaga
nextposition(Lab,[TempPosition|PrevPositions],[[s(X,Y)|Tail],TempPosition|PrevPositions]):-
step(Lab,TempPosition,[s(X,Y)|Tail]),not(member([s(X,Y)|_],PrevPositions)).%nahodim polozenie,
%kotoroe ona mozet dostich za odin shag i proveryaem, chtobi v proidennom puti eshe ni razu ne bilo
%polozeniya zmeiki, v kotorom ee golova sovpadaet s golovoi tekushego polozeniya
%sam predicat poiska v shirinu
%esli golova zmei v poslednem polozenii zmeiki v pervom iz rassmatrivaemih putei sovpadaet s konechnim polem,
%to etot samii pervii put i yavlyaetsya resheniem i prosto vivodim ego
search(Lab,[[[s(X,Y)|SnakeTail]|PrevPositions]|_]):-member(l('O',X,Y),Lab),!,printway(Lab,[[s(X,Y)|SnakeTail]|PrevPositions]).
%esli ze ne sovpadaet, to generim vse puti, kotorii mozno poluchit iz pervogo za odin shag
%i vstavlyaem ih v konec spiska vseh vozmoznih putei, posle chego prodolzaem poisk
search(Lab,[Way|OtherWays]):-
findall(NewWay,nextposition(Lab,Way,NewWay),NewWays),
append(OtherWays,NewWays,AllWays),
search(Lab,AllWays).
%predicat vivoda puti
%poskolku put dlya realizacii algoritma hranitsya v obratnom poryadke, to i vivodim spisok v obratnom poryadke
printway(_,[]):-nl,nl,nl,write("RESHENIE:\n").
printway(Lab,[H|Tail]):-printway(Lab,Tail),printlab(Lab,1,1,H),nl,nl,nl.
goal
write("VVEDITE SHEMU LABIRINTA 10x10. # - STENKA, _ - STENKI NET. I - VHOD, O - VIHOD.\n"),
readlab(Lab,1),
write("VVEDITE DLINU ZMEIKI (OT 5 do 10): "),
readint(N),findway(Lab,N).
Версия с лабиринтом заданным в коде:
%Dannaya programma napisana dlya polya 5x5, dlya polya 10x10 nado ispravit vse
%vstrechayushiesya v programme cifri 6 na 11. Ne ochen sovetuyu eto delat, a takze
%sovetuyu vvodit labirint s kak mozno bolshim kolichestvom stenok, poskolku esli slihkom
%mnogo vozmoznuh putei dlya zmeiki, to mozet ne hvatit razmerov steka pamayti
domains
labfield=l(char,integer,integer) %kazdoe pole hranitsya v vide l(Znak, Koordinata Y, Koordinata X).
labirint=labfield* %labirint - eto spisok polei
snakefield=s(integer,integer). %pole,zanimaemoe zmeikoi hranitsya kak s(Koordinata Y, Koordinata X).
snake=snakefield* %zmeika - spisok sootvetstvuyushih polei
way=snake* %put, proidennii zmeikoi - spisok polozenii zmeiki
ways=way* %puti - spisok putei
predicates
%readlab(labirint,integer).
genlab(labirint).
nondeterm printlab(labirint,integer,integer,snake).
%string_to_list(string,integer,integer,labirint).
append(labirint,labirint,labirint).
append(ways,ways,ways).
nondeterm member(labfield,labirint).
nondeterm member(snakefield,snake).
nondeterm member(snake,way).
gensnake(integer,integer,integer,snake).
nondeterm findway(labirint,integer).
nondeterm nextposition(labirint,way,way).
nondeterm nextfield(integer,integer,integer,integer).
nondeterm step(labirint,snake,snake).
nondeterm search(labirint,ways).
dellast(snake,snake).
nondeterm printway(labirint,way).
nondeterm empty(labirint,integer,integer).
countbends(snake,integer).
clauses
genlab([l('I',1,1),l('_',1,2),l('#',1,3),l('#',1,4),l('#',1,5),
l('#',2,1),l('_',2,2),l('#',2,3),l('#',2,4),l('#',2,5),
l('#',3,1),l('_',3,2),l('_',3,3),l('_',3,4),l('#',3,5),
l('#',4,1),l('#',4,2),l('#',4,3),l('_',4,4),l('#',4,5),
l('#',5,1),l('#',5,2),l('#',5,3),l('_',5,4),l('O',5,5)]).
%predikat, proveryayushii yavlyaetsya li pervii parametr elementom spiska - vtorogo parametra
member(H,[H|_]). %esli on sovpadaet s golovoi, to da
member(H,[_|Tail]):-member(H,Tail). %esli yavlyaetsya elementov hvosta, to da
%predicat, obiedinyayushii dva spiska
append([],B,B). %esli pervii spisok pustoi, to rezultat - vtotoi spisok
append([H|Tail],B,[H|NewTail]):-append(Tail,B,NewTail). %esli ne pustoi, to rekursivno obiedinyaem hvost i vtoroi spisok
%predicat, perevodyashii schitannuyu stroku v spisok polei
%string_to_list("",_,_,[]):-!.%esli stroka pusta, to i spisok pust
%esli ne pusta, to berem pervii simvol stroki, zapisivaem v nuznom formate, uvelichivaem schetchik,
%harakterizuyushii X koordinatu polya na 1 i rekursivno perevodim ostavshuyusya chast stroki
%string_to_list(S,I,J,[l(C,I,J)|Tail]):-frontchar(S,C,STail),J1=J+1,string_to_list(STail,I,J1,Tail).
%schitivanie vsego labirinta
%readlab([],6):-!.%esli doshli do schitivaniya 6i stroki, to otvet pustoi spisok
%inache shitivaem stroku pod nomerom I, perevodim ee v spisok, uvelichivaem nomer stroki na 1,
%rekursivno schitivaem ostavshuyusya chast labirinta, i slivaem vmeste poluchivshiesya spiski polei
%readlab(L,I):-readln(S),string_to_list(S,I,1,H),I1=I+1,readlab(Tail,I1),append(H,Tail,L).
%predikat, vivodyashii labirint, uchitivaya polozenie zmeiki
printlab(_,6,_,_):-!.%esli nomer stroki raven 6, to ostanavlivaemsya
printlab(Lab,I,6,Snake):-!,nl,I1=I+1,printlab(Lab,I1,1,Snake).%esli nomer simvola v stroke raven 6,
%to uvelichivaem nomer stroki i vivodim ostavshuyusya chast labirinta
%esli tekushee pole yavlyaetsya takze polem, zanimaemim zmeikoi, to vivodim * i ostavshuyusya chast labirinta
printlab(Lab,I,J,Snake):-member(s(I,J),Snake),!,write('*'),J1=J+1,printlab(Lab,I,J1,Snake).
%esli ze ne zanyato zmeikoi, to vivodim to, chto hranitsya s spiske polei labirinta
printlab(Lab,I,J,Snake):-member(l(C,I,J),Lab),write(C),J1=J+1,printlab(Lab,I,J1,Snake).
%predikat, generyashii nachalnoe polozenie zmeiki zadannoi dlini. Schitaem, chto iznachalno ona zanimaet odno pole
gensnake(_,_,0,[]):-!. %esli dlina ravna 0, to spisok pust
gensnake(X,Y,N,[s(X,Y)|Tail]):-N1=N-1,gensnake(X,Y,N1,Tail). %inache generim pole s zadannimi koordinatami i rekursivno generim hvost
%predicat poiska puti. Nahodit koordinati vhoda v labirint, generit zmeiku na etom pole i zapuskaet predicat poiska
%Poskolku nado naiti kratchaishii put, to ispolzuetsya posik v shirinu.
findway(Lab,N):-member(l('I',X,Y),Lab),gensnake(X,Y,N,Snake),search(Lab,[[Snake]]).
%predicat, vozvrashayushii koordinati polya, na kotoroe teoreticheski mozet peremistitsya zneika s zadannogo polya
nextfield(X,Y,X,Y1):-Y1=Y+1;Y1=Y-1.
nextfield(X,Y,X1,Y):-X1=X+1;X1=X-1.
%predicat dlya udaleniya poslednego elementa spiska
dellast([_],[]):-!.
dellast([H|Tail],[H|NewTail]):-dellast(Tail,NewTail).
%predicat, proveryayushii yavlyaetsya li zadannoe pole pustim
empty(Lab,A,B):-member(l('_',A,B),Lab);member(l('O',A,B),Lab).
%predicat, schitiyushii kolichestvo izgibov v zmeike
countbends([_,_],0):-!.%esli dlina menshe 3, to otvet 0
%esli pervaya koordinata pervih treh sovpadaet, to oni ne obrazutyu igib, prosto rekursivno smotrim dalshe
countbends([s(X,_),s(X,Y2),s(X,Y3)|Tail],N):-!,countbends([s(X,Y2),s(X,Y3)|Tail],N).
%analogichno so vtoroi koordinatoi
countbends([s(_,Y),s(X2,Y),s(X3,Y)|Tail],N):-!,countbends([s(X2,Y),s(X3,Y)|Tail],N).
%syuda iz-za otsecheniya popadaem tolko esli ne vipolneno ni odno iz pervih treh pravil,
%znachit izgib suchestvuet i kolichestvo izgobov, poluchennih posle rekursivnogo vizova, neobhodimo uvelichet na 1
countbends([_,s(X2,Y2),s(X3,Y3)|Tail],N1):-countbends([s(X2,Y2),s(X3,Y3)|Tail],N),N1=N+1.
%predicat, generyashii polozenie zmeiki posle togo, kak ona sdelaet odin dopustimii shag
step(Lab,[s(X,Y)|Tail],[s(A,B),s(X,Y)|NewTail]):-
nextfield(X,Y,A,B),empty(Lab,A,B),%nahodim potencialnoe sleduyushee pole, proveryaem ego na pustotu
dellast(Tail,NewTail),countbends([s(A,B),s(X,Y)|NewTail],N),N<3. %udalyaem poslednii element zmeiki,
%schitaem kolichestvo izgibov, i proveryaem, chtobi ono bilo menshe 3
%predicat, generyashii dlya zadannogo puti zmeiki, put, kotorii ona mozet proiti s uchetom sleduyushego shaga
nextposition(Lab,[TempPosition|PrevPositions],[[s(X,Y)|Tail],TempPosition|PrevPositions]):-
step(Lab,TempPosition,[s(X,Y)|Tail]),not(member([s(X,Y)|_],PrevPositions)).%nahodim polozenie,
%kotoroe ona mozet dostich za odin shag i proveryaem, chtobi v proidennom puti eshe ni razu ne bilo
%polozeniya zmeiki, v kotorom ee golova sovpadaet s golovoi tekushego polozeniya
%sam predicat poiska v shirinu
%esli golova zmei v poslednem polozenii zmeiki v pervom iz rassmatrivaemih putei sovpadaet s konechnim polem,
%to etot samii pervii put i yavlyaetsya resheniem i prosto vivodim ego
search(Lab,[[[s(X,Y)|SnakeTail]|PrevPositions]|_]):-member(l('O',X,Y),Lab),!,printway(Lab,[[s(X,Y)|SnakeTail]|PrevPositions]).
%esli ze ne sovpadaet, to generim vse puti, kotorii mozno poluchit iz pervogo za odin shag
%i vstavlyaem ih v konec spiska vseh vozmoznih putei, posle chego prodolzaem poisk
search(Lab,[Way|OtherWays]):-
findall(NewWay,nextposition(Lab,Way,NewWay),NewWays),
append(OtherWays,NewWays,AllWays),
search(Lab,AllWays).
%predicat vivoda puti
%poskolku put dlya realizacii algoritma hranitsya v obratnom poryadke, to i vivodim spisok v obratnom poryadke
printway(_,[]):-nl,nl,nl,write("RESHENIE:\n").
printway(Lab,[H|Tail]):-printway(Lab,Tail),printlab(Lab,1,1,H),nl,nl,nl.
goal
%write("VVEDITE SHEMU LABIRINTA 10x10. # - STENKA, _ - STENKI NET. I - VHOD, O - VIHOD.\n"),
%readlab(Lab,1),
genlab(Lab),
write("VVEDITE DLINU ZMEIKI (OT 5 do 10): "),
readint(N),findway(Lab,N).
|
Главная
Каталог файлов
