Программа поиска пути в лабиринте

@Victor35 · Регистрация: 21.04.2009

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

Здравствуйте! Задали в универе написать программу на Билдере, которая бы искала путь в лабиринте. Лабиринт может задаваться как интерактивно, так и загружаться из файла. Лабиринт задается через StringGrid (можно задавать проходы 0, а стены 1). Я только начал изучение Билдера, поэтому многого не понимаю. Пока моих способностей хватило только чтобы компонентов навставлять и задавать лабиринт интерактивно. Вот моё начало, может кто дальше поможет:

C++
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
#include <vcl.h>
#pragma hdrstop
 
#include "Unit7.h"
 
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
 
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::FormCreate(TObject *Sender)
{
StringGrid1->FixedRows = 0;
StringGrid1->FixedCols = 0;
StringGrid1->RowCount = StrToInt(Edit1->Text);
StringGrid1->ColCount = StrToInt(Edit2->Text);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::StringGrid1SelectCell(TObject *Sender, int ACol,
int ARow, bool &CanSelect)
{
StringGrid1->Cells[ACol][ARow]=Edit3->Text;
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::StringGrid1DblClick(TObject *Sender)
{
StringGrid1->RowCount = StrToInt(Edit1->Text);
StringGrid1->ColCount = StrToInt(Edit2->Text);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 
}
//---------------------------------------------------------------------------

@Toxa33rus · 21.04.2009, 20:28

Если вход и выход из лабиринта находится по периметру (не внутри - аля телепорт), то можно идти по любой стене и когда-нибудь придешь к выходу. Т.е. условно хватаешься левой рукой за стену и идешь не отпуская ее.

Evg · 21.04.2009, 20:47

Сообщение от Toxa33rus

Если вход и выход из лабиринта находится по периметру (не внутри - аля телепорт), то можно идти по любой стене и когда-нибудь придешь к выходу. Т.е. условно хватаешься левой рукой за стену и идешь не отпуская ее.

Необязательно попадёшь к выходу. Можешь пройти по кругу и вернуться обратно

@Victor35 · 22.04.2009, 15:20 **[ТС]**

А почему мне например Билдер не позволяет написать следующее:

C++
1
2
3
4
5
6
void __fastcall TForm1::Button1Click(TObject *Sender)
{
for (int j=0; j<StringGrid1->ColCount; j++)
        for (int i=0; i<StringGrid1->RowCount; i++)
              if (StringGrid1->Cells[j][i]==0) then StringGrid1->Cells[j][i]=1;
}

а он мне указывает на строчку:

C++
1
if (StringGrid1->Cells[j][i]==0) then StringGrid1->Cells[j][i]=1;

и говорит что не понимает что такое i и j. Что я делаю неправильно?

@Jazon_deenAlt · 22.04.2009, 15:40

Хз поможет ли опишу возможный алгоритм... карочь представь себе матрицу Н*М(число к) елементов. Пусть значение ячеек: 0-стена, 1-проход, 2-начало откуда пойдем, Н*М-конечный пункт. Например мы рандомно задали стены/проходы и получили некую матрицу:
01010
01001
10100
01010
10101
терь зададим начало и конец, получим:
21010
01001
10100
01010
10к01
терь тыцаем найтить путь, оно ищет путь по принцыпу "а куда мне можно пойтить?" туда куда можно пишем значение "3" получим после первого перерисова:
23010
03001
10100
01010
10к01
терь цыклим до победной с точки 3 к "к" с шагом +1 получим:
23010
03001
40400
05050
60к06
Надо бы теперь ввести такое что бы следующий шаг при натолкнении на меньшый результат и невозможности куда-то пойти стирал себя:
2*010
03001
40400
05050
*0к0*
Итог рисуем путь от 2 к "к":
2*010
0-001
-0-00
0-0-0
*0к0*
ето есть волновой алгоритм поиска пути... в простом виде)

Evg · 22.04.2009, 16:47

Сообщение от Victor35

А почему мне например Билдер не позволяет написать следующее:

Видимо, всё очень плохо...
После второй втроки вставь "int i, j;"

@Victor35 · 23.04.2009, 22:20 **[ТС]**

А зачем? У меня же в циклах for указано, что i и j являются int.

Evg · 23.04.2009, 22:22

Сообщение от Victor35

А зачем? У меня же в циклах for указано, что i и j являются int.

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

@Victor35 · 25.04.2009, 20:25 **[ТС]**

Он пишет, что неизвестный символ THEN и что он ожидает точку с запятой в этом месте (ну то есть где then написано)

@Фенрир · 25.04.2009, 21:28

then - нету в c++ такого ключевого слова

@Victor35 · 27.04.2009, 23:01 **[ТС]**

Сообщение от Фенрир

then - нету в c++ такого ключевого слова

А! Точно! Спасибо! Никто не натыкался на реализацию волнового алгоритма на каком нибудь языке? Если да, то пришлите ссылку пожалуйста.

@Jazon_deenAlt · 29.04.2009, 09:47

вот она! и заметте далеко идти не надо) Клеточная карта

@BOR1K · 27.01.2010, 14:01

Надо поднять тему. На форуме еще нет решения лабиринта(

Evg · 27.01.2010, 14:15

Ищи алгоритмы "перебор в ширину", "перебор в глубину", "полный перебор". Любым алгоритмом перебора ты выход найдёшь

@BOR1K · 27.01.2010, 15:12

Не, сейчас актуален волновой алгоритм.(Алгоритм Ли)

@22dr22 · 27.01.2010, 17:18

ловіть))))))))))))))))))))))))
//---------------------------------------------------------------------------

C++
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
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int kil;
typedef int dr[100][100];
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
void find(dr m, int x,int y,int r,int s)
{
if ((x==s-1) && (y==r-1))
    kil++;
    else
    {
    if (y+1<r)
        if (m[y+1][x]==1)
           find(m,x,y+1,r,s);
    if (x+1<s)
        if (m[y][x+1]==1)
           find(m,x+1,y,r,s);
    }
}
 
void __fastcall TForm1::CSpinEdit1Change(TObject *Sender)
{
table->ColCount=CSpinEdit1->Value;
Button1->Click() ;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::CSpinEdit2Change(TObject *Sender)
{
table->RowCount=CSpinEdit2->Value;
Button1->Click() ;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::N1Click(TObject *Sender)
{
int i,j,r=CSpinEdit1->Value, s=CSpinEdit2->Value;
dr dr1;
kil=0;
for (i=0;i<s;i++)
 for (j=0;j<r;j++)
     dr1[i][j]=StrToInt(table->Cells[j][i]);
find(dr1,0,0,s,r);
Edit1->Text="Кількість можливих шляхів = "+IntToStr(kil);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
for (int i=0;i<table->ColCount ;i++)
for (int j=0;j<table->ColCount ;j++)
table->Cells [i][j]="0";
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Form1->Close() ;
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::FormCreate(TObject *Sender)
{
Button1->Click() ;
}
//---------------------------------------------------------------------------

Добавлено через 2 минуты
путь задается 1ми =))))))))))))
table - StringGrid

Добавлено через 27 секунд
Рекурсия - это вещь))))))))

@BOR1K · 27.01.2010, 19:15

А слабо сделать без формы? т.е. в консоли к примеру, 1- стены, 0 путь, 2 начальная точка,3 конечная, я в свое время делал) тока кода нет(

@22dr22 · 27.01.2010, 19:32

в чем проблемма????
вместо стрынггрида - масив int table[][];
у меня начало лабиринту в [0][0], конец в правом нижнем углу, если кто не понял..

у меня такое впечетление что ты BOR1K вообще не писал такую программу, так как твой вопрос - свидетельствует об этом!!!!
"а без формы слабо" - БУГАГА)

Evg · 27.01.2010, 20:19

22dr22, скорее всего он имел в виду то, что твою программу без доработки напильником не запустить. Вот когда можно взять код и тупо его скомпилять - это одно. А когда надо плясать с бубном и разбираться, как твою программу повторить у себя - другое. Лично меня совершенно ломает что-то делать с твоей программой

@22dr22 · 27.01.2010, 20:26

=))))))
find - ф-я поиск
просит матрицу(лабиринт) координати начала и конца =))))

код то мелкий, 1,5 экрана =))))

да ты прав надо было спросить ТЗ - написать и скинуть проэкт за спасибо =)))))

я кинул пример - тот кому нужен - поймет и свой напишет, а для халявщиков я делать не буду =))))

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@Toxa33rus 3924 / 925 / 125 Регистрация: 16.04.2009 Сообщений: 1,975
	21.04.2009, 20:28
	Если вход и выход из лабиринта находится по периметру (не внутри - аля телепорт), то можно идти по любой стене и когда-нибудь придешь к выходу. Т.е. условно хватаешься левой рукой за стену и идешь не отпуская ее. 0

@Jazon_deenAlt 4117 / 999 / 191 Регистрация: 09.04.2009 Сообщений: 4,223
	22.04.2009, 15:40
	Хз поможет ли опишу возможный алгоритм... карочь представь себе матрицу НМ(число к) елементов. Пусть значение ячеек: 0-стена, 1-проход, 2-начало откуда пойдем, НМ-конечный пункт. Например мы рандомно задали стены/проходы и получили некую матрицу: 01010 01001 10100 01010 10101 терь зададим начало и конец, получим: 21010 01001 10100 01010 10к01 терь тыцаем найтить путь, оно ищет путь по принцыпу "а куда мне можно пойтить?" туда куда можно пишем значение "3" получим после первого перерисова: 23010 03001 10100 01010 10к01 терь цыклим до победной с точки 3 к "к" с шагом +1 получим: 23010 03001 40400 05050 60к06 Надо бы теперь ввести такое что бы следующий шаг при натолкнении на меньшый результат и невозможности куда-то пойти стирал себя: 2010 03001 40400 05050 0к0* Итог рисуем путь от 2 к "к": 2010 0-001 -0-00 0-0-0 0к0* ето есть волновой алгоритм поиска пути... в простом виде) 0

@Victor35 0 / 0 / 0 Регистрация: 21.04.2009 Сообщений: 25
	23.04.2009, 22:20 [ТС]
	А зачем? У меня же в циклах for указано, что i и j являются int. 0

@Victor35 0 / 0 / 0 Регистрация: 21.04.2009 Сообщений: 25
	25.04.2009, 20:25 [ТС]
	Он пишет, что неизвестный символ THEN и что он ожидает точку с запятой в этом месте (ну то есть где then написано) 0

@Фенрир 43 / 39 / 12 Регистрация: 05.01.2009 Сообщений: 394
	25.04.2009, 21:28
	then - нету в c++ такого ключевого слова 0

@Jazon_deenAlt 4117 / 999 / 191 Регистрация: 09.04.2009 Сообщений: 4,223
	29.04.2009, 09:47
	вот она! и заметте далеко идти не надо) Клеточная карта 0

@BOR1K 14 / 14 / 3 Регистрация: 19.09.2009 Сообщений: 289
	27.01.2010, 14:01
	Надо поднять тему. На форуме еще нет решения лабиринта( 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	27.01.2010, 14:15
	Ищи алгоритмы "перебор в ширину", "перебор в глубину", "полный перебор". Любым алгоритмом перебора ты выход найдёшь 0

@BOR1K 14 / 14 / 3 Регистрация: 19.09.2009 Сообщений: 289
	27.01.2010, 15:12
	Не, сейчас актуален волновой алгоритм.(Алгоритм Ли) 0

@BOR1K 14 / 14 / 3 Регистрация: 19.09.2009 Сообщений: 289
	27.01.2010, 19:15
	А слабо сделать без формы? т.е. в консоли к примеру, 1- стены, 0 путь, 2 начальная точка,3 конечная, я в свое время делал) тока кода нет( 0

@22dr22 6 / 6 / 0 Регистрация: 31.12.2009 Сообщений: 132
	27.01.2010, 19:32
	в чем проблемма???? вместо стрынггрида - масив int table[][]; у меня начало лабиринту в [0][0], конец в правом нижнем углу, если кто не понял.. у меня такое впечетление что ты BOR1K вообще не писал такую программу, так как твой вопрос - свидетельствует об этом!!!! "а без формы слабо" - БУГАГА) 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	27.01.2010, 20:19
	22dr22, скорее всего он имел в виду то, что твою программу без доработки напильником не запустить. Вот когда можно взять код и тупо его скомпилять - это одно. А когда надо плясать с бубном и разбираться, как твою программу повторить у себя - другое. Лично меня совершенно ломает что-то делать с твоей программой 0

@22dr22 6 / 6 / 0 Регистрация: 31.12.2009 Сообщений: 132
	27.01.2010, 20:26
	=)))))) find - ф-я поиск просит матрицу(лабиринт) координати начала и конца =)))) код то мелкий, 1,5 экрана =)))) да ты прав надо было спросить ТЗ - написать и скинуть проэкт за спасибо =))))) я кинул пример - тот кому нужен - поймет и свой напишет, а для халявщиков я делать не буду =)))) 0