Выход из лабиринта

@SwEEt_LOLi · Регистрация: 24.10.2016

Студворк — интернет-сервис помощи студентам

Помогите допилить.Нужен алгоритм нахождения выхода и лабиринта.За ранее спасибо!
Вот сам лабиринт:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
uses GraphABC;
const
  szw=70;
  szh=50;
  cellsz=10;
type
  point=record
    x,y: integer;
  end;
var
  maze: array [0..szw-1] of array [0..szh-1] of integer;
  todo: array [0..szw*szh-1] of point;
  todonum: integer;
const
  dx: array [0..3] of integer=(0, 0, -1, 1);
  dy: array [0..3] of integer=(-1, 1, 0, 0);
procedure init;
var
  x,y,n,d: integer;
begin
  for x:=0 to szw-1 do
  for y:=0 to szh-1 do
    if (x=0) or (x=szw-1) or (y=0) or (y=szh-1) then
      maze[x][y]:=32
    else maze[x][y]:=63;
  Randomize;
  x := Random(szw-2)+1;
  y := Random(szh-2)+1;
  maze[x][y]:= maze[x][y] and not 48;
  for d:=0 to 3 do
    if (maze[x + dx[d]][y + dy[d]] and 16) <> 0 then
    begin
      todo[todonum].x:=x + dx[d];
      todo[todonum].y:=y + dy[d];
      Inc(todonum);
      maze[x + dx[d]][y + dy[d]] := maze[x + dx[d]][y + dy[d]] and not 16;
    end;
   while todonum > 0 do
   begin
       n:= Random(todonum);
       x:= todo[n].x;
       y:= todo[n].y;
       Dec(todonum);
       todo[n]:= todo[todonum];
       repeat
           d:=Random (4);
       until not ((maze[x + dx[d]][y + dy[d]] and 32) <> 0);
       maze[x][y] := maze[x][y] and not ((1 shl d) or 32);
       maze[x + dx[d]][y + dy[d]] := maze[x + dx[d]][y + dy[d]] and not (1 shl (d xor 1));
       for d:=0 to 3 do
           if (maze[x + dx[d]][y + dy[d]] and 16) <> 0 then
           begin
             todo[todonum].x := x + dx[d];
             todo[todonum].y := y + dy[d];
             Inc(todonum);
             maze[x + dx[d]][y + dy[d]] := maze[x + dx[d]][y + dy[d]] and not 16;
           end;
   end;
   maze[1][1] := maze[1][1] and not 1;
   maze[szw-2][szh-2] := maze[szw-2][szh-2] and not 2;
end;
procedure Draw;
var x,y: integer;
begin
  for x:=1 to szw-2 do
  for y:=1 to szh-2 do
  begin
   if ((maze[x][y] and 1) <> 0) then
       Line(x * cellsz, y * cellsz, x * cellsz + cellsz + 1, y * cellsz);
   if ((maze[x][y] and 2) <> 0) then
       Line(x * cellsz, y * cellsz + cellsz, x * cellsz + cellsz + 1, y * cellsz + cellsz);
   if ((maze[x][y] and 4) <> 0) then
       Line(x * cellsz, y * cellsz, x * cellsz, y * cellsz + cellsz + 1);
   if ((maze[x][y] and 8) <> 0) then
       Line(x * cellsz + cellsz, y * cellsz, x * cellsz + cellsz, y * cellsz + cellsz + 1);
  end;
end;
begin
  SetWindowCaption('Генерация лабиринта');
  init;
  draw;
end.

ФедосеевПавел · 24.10.2016, 20:38

Тут все зависит от вашей подготовки.
На школьном уровне считается нормальным поиск выхода рекурсивным поиском в глубину.
Пример из книги "Московские олимпиады по программированию":

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
{
Лабиринт.
  Может ли путник выйти из лабиринта? Если может, то напечатать путь
от выхода до начального положения путника.
  Лабиринт задан массивом A размером 40x40, в котором:
  A[k, m]=0, если клетка [k, m] "проходима";
  A[k, m]=1, если клетка [k, m] "непроходима".
 
  Начальное положение путника задаётся в проходимой клетке [i, j].
Путник может перемещаться из одной проходимой клетки в другую, если
они имеют общую сторону. Путник выходит из лабиринта, когда попадает
в граничную клетку (то есть клетку [k, m], где k или m равны 1 или 40).
}
 
{$define NoInput}{данные для задачи не вводить, а взять из констант}
program OLI833;
 
const
  MM = 15;
  NN = 15;
type
  TMaze = array [1..MM, 1..NN] of byte;
var
  vyh: boolean;
{$ifndef NoInput}
  m, n,
  i, j : Integer;
  A    : TMaze;
{$endif}
{$ifdef NoInput}
const
  m: integer = 5;
  n: integer = 5;
  i: integer = 3;
  j: integer = 3;
  A: TMaze =
    (
    (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 1}
    (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 2}
    (1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 3}
    (1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 4}
    (1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 5}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 6}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 7}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 8}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   { 9}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   {10}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   {11}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   {12}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   {13}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),   {14}
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)    {15}
    );
 
{$endif}
 
  procedure L(i, j: integer);
  begin
    if not vyh then
      if A[i, j] = 0 then
      begin
        if (i = 1) or (i = m) or (j = 1) or (j = n) then
          vyh := True;
        A[i, j] := 1;
        L(i, j - 1);
        L(i, j + 1);
        L(i - 1, j);
        L(i + 1, j);
        if vyh then
          WriteLn(i, ' ', j);
      end;
  end;
 
begin
{$ifndef NoInput}
  WriteLn('M, N:=');
  ReadLn(m, n);
  for i:=1 to m do
    for j:=1 to n do begin
      Write('A[', i, ',', j, ']:=');
      ReadLn(A[i, j]);
    end;
  WriteLn;
  WriteLn('I, J:=');
  ReadLn(i, j);
  WriteLn;
{$endif}
  vyh := False;
  L(i, j);
  if not vyh then
    WriteLn('net vyhoda');
end.

Если нужен кратчайший путь - то его находят Алгоритмом Ли - https://ru.wikipedia.org/wiki/Алгоритм_Ли (в этой статье есть ссылка на Викиучебник с реализацией https://ru.wikibooks.org/wiki/... 0%9B%D0%B8

Движение по лабиринту: Определить и вывести на экран кратчайшее расстояние

А если поискать по форуму "расширенным поиском" только в разделе Pascal можно найти множество реализаций поиска пути из лабиринта, они все разные и очень интересные. Помню, что с интересом знакомился с большинством реализаций.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .