Найти выход в лабиринте

Компьютерная программа прохождения лабиринта

Задача прохождения лабиринта описывалась неоднократно и пересказывать сказанное мы не будем. Разновидности лабиринтов и методы их прохождения подробно описаны на различных сайтах Интернета.

Кратко остановимся только на следующем правиле прохождения лабиринта.

Правило «одной руки»

Правило «одной руки» является одним из самых простых для прохождения лабиринта, суть которого сводится к алгоритму: двигаясь по лабиринту, надо все время касаться правой (или левой) рукой его стены. Придется пройти не самый короткий путь, заходя во все тупики, но в итоге цель будет достигнута.

Последовательность действий робота при проходе лабиринта такова:

В начале робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду. После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом «правой руки». Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа. Если прохода нет — впереди стена — робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

Если у лабиринта нет замкнутых маршрутов, по которым можно возвращаться в исходную точку, то такой лабиринт называют односвязным и его всегда можно обойти полностью, применив правило «одной руки».

Блок-схема алгоритма для робота, работающего по правилу «правой руки», представлена и подробно описана на сайтах Интернета.

Ниже представлены три программы прохождения лабиринта по указанному методу, написанные на языках C, Pascal и Delphi.

Программа прохождения лабиринта на языке C

#include
 #include
 #include
 #include

int n1=15;
 int n2=35;
 float proc=0.67;
 int coordx=(80-n2)/2+1;
 int coordy=(25-n1)/2+1;
 char locked='█';
 char unlocked ='░';
 char man ='¤';
 char way ='∙';
 char subway ='X';

typedef char mas[16][36];
 typedef mas masptr;

mas labirint;
 masptr labirptr;

int i,j,k;
 void inputlabir(masptr l);
 void showlabir(masptr l);

main()
 {
 typedef struct{
 int i,j;} coord;
 typedef coord trasa[1000];
 trasa tr;
 int tn;
 inputlabir(labirptr);
 i=1;j=1;
 labirptr[i][j]='M';
 tn=0;
 showlabir(labirptr);
 do
 {
 if ((i!=n1) && (labirptr[i+1][j]=='O'))
 {
 labirptr[i][j]='1';tn++;tr[tn].i=i;
 tr[tn].j=j;i++;labirptr[i][j]='M';
 }
 else
 if ((j!=n2) && (labirptr[i][j+1]=='O'))
 {
 labirptr[i][j]='1';tn++;tr[tn].i=i;
 tr[tn].j=j;j++;labirptr[i][j]='M';
 }
 else
 if ((i!=1) && (labirptr[i-1][j]=='O'))
 {
 labirptr[i][j]='1';tn++;tr[tn].i=i;
 tr[tn].j=j;i--;labirptr[i][j]='M';
 }
 else if ((j!=1) && (labirptr[i][j-1]=='O'))
 {
 labirptr[i][j]='1';tn++;tr[tn].i=i;
 tr[tn].j=j;j--;labirptr[i][j]='M';
 }
 else
 {
 if (tn==0)
 {
 textcolor(15);textbackground(4);
 gotoxy(24,22);cprintf(" Кажется, отсюда нет выхода !!! ");
 gotoxy(24,23);cprintf("    Я окончательно погиб !!!    ");
 do {} while (!getch());
 exit(0);
 }
 labirptr[i][j]='2';
 i=tr[tn].i;j=tr[tn].j;tn--;labirptr[i][j]='M';
 }

showlabir(labirptr);delay(100);
 }
 while ((i!=n1) || (j!=n2));
 textcolor(15);textbackground(2);
 gotoxy(24,22);cprintf(" УРА !!!  Я выбрался отсюда !!! ");
 gotoxy(24,23);cprintf("     Моя жизнь спасена !!!      ");
 do {} while (!getch());
 }

void inputlabir(masptr l)
 {
 int i,j,k,kol;
 char c;
 textbackground(0); clrscr(); textcolor(14);
 gotoxy(30,3);cprintf("Л  А  Б  И  Р  И  Н  Т");
 for (i=1;i l[1][1]='O';l[n1][n2]='O';
 i=1;j=2;k=2;
 kol=((proc+0.5)*(n1)*(n2));
 gotoxy(1,25);textcolor(0);textbackground(7);
 cprintf("-проход |-стенка |-завершение ввода |-выход |-random");
 textbackground(0);
 do
 {
 showlabir(l);
 gotoxy(j+coordx-1,i+coordy-1);
 do
 {
 c=getch();
 }
 while ((c!='\x20')&&(c!='z')&&(c!='\x0')&&(c!='\x1B')&&(c!='\xD'));
 switch(c)
 {
 case '\x0' :{switch (getch())
 {
 case '\x3B':randomize();
 while (k {
 i=1+random(n1);j=1+random(n2);
 if (l[i][j]!='O')
 {
 l[i][j]='O';
 showlabir(l);
 }
 k=k+1;
 }
 c='\xD';
 break;
 case '\x50':i=i+1;if (i==(n1+1)) i=1;break;
 case '\x48':i=i-1;if (i==0) i=n1;break;
 case '\x4B':j=j-1;if (j==0) j=n2;break;
 case '\x4D':j=j+1;if (j==(n2+1)) j=1;break;
 };break;
 }
 case '\x1B': exit(0);break;
 case '\x20': if (l[i][j]!='O') l[i][j]='O';k=k+1;break;
 case 'z'   : if (l[i][j]!='3') l[i][j]='3';k=k-1;break;
 }
 //    c=getch();
 }
 while (c!='\xD');
 }

void showlabir(masptr l)
 {
 int i,j;
 for (i=1;i {
 gotoxy(coordx,i+coordy-1);
 for (j=1;j {
 switch(l[i][j])
 {
 case '3'  : textcolor(6);cprintf("%c",locked);break;
 case 'O'  : textcolor(8);cprintf("%c",unlocked);break;
 case 'M'  : textcolor(14);cprintf("%c",man);break;
 case '1'  : textcolor(15);cprintf("%c",way);break;
 case '2'  : textcolor(8);cprintf("%c",subway);break;
 }
 }

}
 }

Программа прохождения лабиринта на языке Pascal


program labirint;
 uses crt;
 const
 n1 = 15;
 n2 = 35;
 proc = 0.67; {в сотых долях}
 CoordX = (80-n2) div 2 + 1;
 CoordY = (25-n1) div 2 + 1;
 Locked = '█';
 Unlocked = '░';
 Man = '¤';
 Way = '∙';
 SubWay = 'X';
 type
 mas=array[1..n1,1..n2] of char;
 masptr=^mas;
 var
 labirint:mas;
 labirptr:masptr;
 i,j,k:integer;
 procedure showlabir(l:masptr); forward;
 procedure inputlabir(l:masptr);
 var
 i,j,k,kol:integer;
 c:char;
 begin
 TextBackGround(0);
 clrscr; textcolor(14);
 gotoxy(30,3);write('Л  А  Б  И  Р  И  Н  Т');
 for i:=1 to n1 do for j:=1 to n2 do l^[i,j]:='З';
 l^[1,1]:='О';l^[n1,n2]:='О';
 i:=1;j:=2;k:=2;kol:=round(proc*n1*n2);
 gotoxy(1,25);textcolor(0);textbackground(7);
 write('-проход |-стенка |-завершение ввода |-выход |-random');
 textbackground(0);
 repeat
 showlabir(l);
 GotoXY(j+CoordX-1,i+CoordY-1);
 repeat c:=readkey until c in [' ','z',#0,#27,#13];
 case c of
 #0 : case readkey of
 #59 : begin
 randomize;
 while k begin
 i:=1+random(n1);j:=1+random(n2);
 if l^[i,j]<>'О' then
 begin
 l^[i,j]:='О';
 inc(k);
 showlabir(l)
 end
 end;
 exit
 end;
 #72 : begin dec(i);if i=0 then i:=n1; end; {вверх}
 #75 : begin dec(j);if j=0 then j:=n2; end; {влево}
 #77 : begin inc(j);if j=n2+1 then j:=1; end; {вправо}
 #80 : begin inc(i);if i=n1+1 then i:=1; end; {вниз}
 end;
 #27 : halt(1);
 ' ' : if l^[i,j]<>'О' then begin l^[i,j]:='О';inc(k) end;
 'z' : if l^[i,j]<>'З' then begin l^[i,j]:='З';dec(k) end;
 end;
 until c=#13;
 end;
 procedure showlabir(l:masptr);
 var
 i,j:integer;
 begin
 for i:=1 to n1 do
 begin
 GotoXY(CoordX,i+CoordY-1);
 for j:=1 to n2 do
 begin
 case l^[i,j] of
 'З'     : begin textcolor(6);write(Locked) end;
 'О'     : begin textcolor(8);write(Unlocked) end;
 'М'     : begin textcolor(14);write(Man);end;
 '1'     : begin textcolor(15);write(Way); end;
 '2'     : begin textcolor(8);write(SubWay) end;
 end;
 end
 end
 end;
 type
 coord=record
 i,j:integer;
 end;
 trasa=array[1..1000] of coord;
 var
 tr:trasa;
 tn:integer;

BEGIN
 new(labirptr);
 inputlabir(labirptr);
 i:=1;j:=1;labirptr^[i,j]:='М';tn:=0;
 showlabir(labirptr);
 repeat
 if (i<>n1) and (labirptr^[i+1,j]='О') then
 begin
 labirptr^[i,j]:='1';inc(tn);tr[tn].i:=i;
 tr[tn].j:=j;inc(i);labirptr^[i,j]:='М'
 end
 else if (j<>n2) and (labirptr^[i,j+1]='О') then
 begin
 labirptr^[i,j]:='1';inc(tn);tr[tn].i:=i;
 tr[tn].j:=j;inc(j);labirptr^[i,j]:='М'
 end
 else if (i<>1) and (labirptr^[i-1,j]='О') then
 begin
 labirptr^[i,j]:='1';inc(tn);tr[tn].i:=i;
 tr[tn].j:=j;dec(i);labirptr^[i,j]:='М'
 end
 else if (j<>1) and (labirptr^[i,j-1]='О') then
 begin
 labirptr^[i,j]:='1';inc(tn);tr[tn].i:=i;
 tr[tn].j:=j;dec(j);labirptr^[i,j]:='М'
 end
 else
 begin
 if tn=0 then
 begin
 textcolor(15);textbackground(4);
 gotoxy(24,22);Write(' Кажется, отсюда нет выхода !!! ');
 gotoxy(24,23);Write('    Я окончательно погиб !!!    ');
 repeat until keypressed;
 exit
 end;
 labirptr^[i,j]:='2';
 i:=tr[tn].i;j:=tr[tn].j;dec(tn);labirptr^[i,j]:='М';
 end;
 showlabir(labirptr);delay(100);
 until (i=n1) and (j=n2);
 textcolor(15);textbackground(2);
 gotoxy(24,22);Write(' УРА !!!  Я выбрался отсюда !!! ');
 gotoxy(24,23);Write('     Моя жизнь спасена !!!      ');
 repeat until keypressed;
 END.

Программа прохождения лабиринта на языке Delphi

 

Заказать исходный текст программы прохождения лабиринта на Delphi: azov192@gmail.com

Александр Малыгин

Объект обсуждения - программное обеспечение для выполнения автоматизированного конструкторского и технологического проектирования, разработки управляющих программ, вопросы, связанные с разработкой прикладных САПР.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *