VPF::Поиск кратчайшего пути в лабиринте

cloun

Дата 18.12.2011, 21:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 18.12.2011

Репутация: нет
Всего: нет

Всех приветствую! Делаю задание на C++ Builder 6: найти кратчайший путь в лабиринте от текущего положения до выхода. Лабиринт сделал через StringGrid, где '0' – пустая область, куда можно делать ход, '1' — препятствие. Расставил препятствия вручную, так как иначе можно получить тупиковую ситуацию. Ячейка 1А — начало лабиринта, 5Е — выход. Минимальный путь — 2B, 3C, 4D. Максимальный — 2B, 1B, 1C, 1D, 1E, 2E, 3E, 4E. После нахождения кратчайшего пути заголовку Label присваивается координаты ячеек, входящих в этот самый путь. Понятно, чтобы найти минимальный маршрут, нужно организовать цикл с использованием алгоритма (например, волнового). С этим у меня и возникли проблемы. Почитал, посмотрел похожие темы — не помогло. Возможно, программирование не для меня или сказывается маленький опыт. От не понимания, что делать дальше, посмотрел как суммировать значения всех ячеек. Надеюсь, кто-нибудь подскажет как быть дальше. С уважением, Сергей.

user posted image

Код


// создание лабиринта
Form1->StringGrid1->Cells[0][0]='0'; //start
Form1->StringGrid1->Cells[4][4]='0'; //finish
Form1->StringGrid1->Cells[1][0]='0'; //long way
Form1->StringGrid1->Cells[1][1]='0'; //short way
Form1->StringGrid1->Cells[1][2]='1';
Form1->StringGrid1->Cells[1][3]='1';
Form1->StringGrid1->Cells[1][4]='1';
Form1->StringGrid1->Cells[2][0]='0'; //l
Form1->StringGrid1->Cells[2][1]='1';
Form1->StringGrid1->Cells[2][2]='0'; //s
Form1->StringGrid1->Cells[2][3]='1';
Form1->StringGrid1->Cells[2][4]='1';
Form1->StringGrid1->Cells[3][0]='0'; //l
Form1->StringGrid1->Cells[3][1]='1';
Form1->StringGrid1->Cells[3][2]='1';
Form1->StringGrid1->Cells[3][3]='0'; //s
Form1->StringGrid1->Cells[3][4]='1';
Form1->StringGrid1->Cells[4][0]='0'; //l
Form1->StringGrid1->Cells[4][1]='0'; //l
Form1->StringGrid1->Cells[4][2]='0'; //l
Form1->StringGrid1->Cells[0][1]='1';
Form1->StringGrid1->Cells[0][2]='1';
Form1->StringGrid1->Cells[0][3]='1';
Form1->StringGrid1->Cells[0][4]='1';
Form1->StringGrid1->Cells[4][3]='0'; //l

// суммирование значений всех ячеек
int summa = 0;
  for(int i = 0; i < StringGrid1->ColCount; i++)
    for(int j = 0; j < StringGrid1->RowCount; j++)
      summa += StrToInt(StringGrid1->Cells[i][j]);
Label12->Caption=summa;

Добавлено через 11 минут и 33 секунды
нашел кое-что интересное: "Ставим в начальной точке число 2. Далее просматриваем весь массив. Если встречаем пустую клетку, у которой соседняя клетка равна 2, то ставим в эту клетку число 3. Затем ещё раз просматриваем, но уже ищем 3, а ставим 4. Это продолжается до тех пор, пока не поставим число в клетку конца пути. Если за просмотр не сделано ни одного изменения, то значит пути не существует.В полученной матрице получить все кратчайшие пути - элементарно." Попробую реализовать, как и с суммированием всех значений ячеек.

KTatsu

Дата 24.12.2011, 21:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 42
Регистрация: 23.8.2008
Где: Москва

Репутация: 1
Всего: 1

Не знаю, решил автор или нет, тем не менее, вопрос не помечен как решенный.

Я решил так:

Таблица 10х10, нулевые ряды для имен линий, рабочее пространство лабиринта 9х9.
Обзываю заголовки при создании формы:

Код


StringGrid1->Cells[1][0]="A";
StringGrid1->Cells[2][0]="B";
StringGrid1->Cells[3][0]="C";
StringGrid1->Cells[4][0]="D";
StringGrid1->Cells[5][0]="E";
StringGrid1->Cells[6][0]="F";
StringGrid1->Cells[7][0]="G";
StringGrid1->Cells[8][0]="H";
StringGrid1->Cells[9][0]="I";

for(int i=1;i<10;i++)
    StringGrid1->Cells[0][i]="|"+IntToStr(i)+"|";

Генерирую лабиринт, стены заполняются "X", пустые клетки остаются пустыми:

Код


for(int i=1;i<StringGrid1->RowCount;i++)      
   {
    for(int f=1;f<StringGrid1->ColCount;f++)  
       {
        if(random(2))      
           StringGrid1->Cells[i][f]='X';
        else
           StringGrid1->Cells[i][f]="";
       }
   }
StringGrid1->Cells[1][1]="";           // здесь я очищаю клетки старта и финиша если рандом их заполнил
StringGrid1->Cells[StringGrid1->ColCount-1][StringGrid1->RowCount-1]="";

Используя принцип

Цитата

Ставим в начальной точке число 2. Далее просматриваем весь массив. Если встречаем пустую клетку, у которой соседняя клетка равна 2, то ставим в эту клетку число 3. Затем ещё раз просматриваем, но уже ищем 3, а ставим 4. Это продолжается до тех пор, пока не поставим число в клетку конца пути.

заполняю свободные клетки:

Код


StringGrid1->Cells[1][1]="1";
      for(int j=1;j<(StringGrid1->RowCount-1)*(StringGrid1->ColCount-1);j++)
         {
          for(int i=1;i<StringGrid1->RowCount;i++)     
             {
              for(int f=1;f<StringGrid1->ColCount;f++)  
                 {
                  if(StringGrid1->Cells[i][f]=="")
                    {
                     if((StringGrid1->Cells[i-1][f-1]==j)||
                        (StringGrid1->Cells[i-0][f-1]==j)||
                        (StringGrid1->Cells[i+1][f-1]==j)||
                        (StringGrid1->Cells[i-1][f]==j)||
                        (StringGrid1->Cells[i+1][f]==j)||
                        (StringGrid1->Cells[i-1][f+1]==j)||
                        (StringGrid1->Cells[i][f+1]==j)||
                        (StringGrid1->Cells[i+1][f+1]==j))
                         StringGrid1->Cells[i][f]=j+1;
                    }
                 }
             }
         }

И последний пункт, начиная от точки выхода ищу кратчайший путь по убыванию. Точки записываю в строки Memo.
В клетках найденных точек ставлю значение "F" для наглядности, да и отладить это помогло один глюк smile

Код


Memo1->Clear();
int x=StringGrid1->ColCount-1;
int y=StringGrid1->RowCount-1;
if(StringGrid1->Cells[x][y]!="")
  {
   int cc=StrToInt(StringGrid1->Cells[x][y]);
   for(int i=1;i<StrToInt(StringGrid1->Cells[x][y]);i++)
       Memo1->Lines->Add("");
   StringGrid1->Cells[StringGrid1->ColCount-1][StringGrid1->RowCount-1]="F";         //Заполняю точку финиша и добавляю координату в список
   Memo1->Lines->Add(StringGrid1->Cells[StringGrid1->ColCount-1][0]+":"+IntToStr(StringGrid1->RowCount-1));
   while(cc>0)
     {
      if(StringGrid1->Cells[x-1][y-1]==cc)
        {
         x=x-1;
         y=y-1;
        }
      else
      if(StringGrid1->Cells[x-1][y]==cc)
         x=x-1;
      else
      if(StringGrid1->Cells[x-1][y+1]==cc)
        {
         x=x-1;
         y=y+1;
        }
      else
      if(StringGrid1->Cells[x][y-1]==cc)
         y=y-1;
      else
      if(StringGrid1->Cells[x][y+1]==cc)
         y=y+1;
      else
      if(StringGrid1->Cells[x+1][y-1]==cc)
        {
         x=x+1;
         y=y-1;
        }
      else
      if(StringGrid1->Cells[x+1][y]==cc)
         x=x+1;
      else
      if(StringGrid1->Cells[x+1][y+1]==cc)
        {
         x=x+1;
         y=y+1;
        }
      Memo1->Lines->Strings[cc-1]=StringGrid1->Cells[x][0]+":"+IntToStr(y);
      StringGrid1->Cells[x][y]="F";
      cc=cc-1;
     }
  }
else
  Memo1->Text="Выход не найден!";

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

P.S. Надеюсь более опытные программеры поправят меня, в чем я ошибся.

Это сообщение отредактировал(а) KTatsu - 24.12.2011, 21:50

artsb

Дата 27.12.2011, 07:41 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2280
Регистрация: 17.7.2007
Где: центр Вселенной

Репутация: 39
Всего: 64

Волновой алгоритм: теория и практика.

--------------------

Чем отличается умный человек от мудрого?
Умный - выпутается из любой ситуации.
Мудрый - просто в неё не попадёт.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C++ Builder \| Следующая тема »