VPF::Решение задачи: Поиск пути из лабиринта

VerLinG

Дата 20.4.2008, 17:07 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите пожалуйста с решением задачи! Непонимаю как вообще к ней подступиться....

помогите пожалуйста с решением и реализацией ((((
Задача такова, что есть массив ( предположим 8х8) в котором все элементы либо 0 либо 1
0 - это "закрытая" область, 1- "открытая" . Все это представляет собой лабиринт, из которого нужно найти выход ( начальные и конечные координаты должны задаваться
Все что я реализовал на данный момент, это создал класс "точка" в котором хранятся координаты элементов массива, значение в которых 1. Но вот как выстроить их в последовательность я не знаю ((( К слову, для выстраивания желательно испольховать стек , но опять же не знаю как алгоритмически продумать это...Вообще это как то надо сделать через библиотеку STL (((

LostSoul

Дата 20.4.2008, 17:47 (ссылка)

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

Загрузка ...

Новичок

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

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

http://algolist.manual.ru/games/wavealg.php
STL можно использовать для хранения координат точек волны, например, в стеке

Это сообщение отредактировал(а) LostSoul - 20.4.2008, 17:48

VerLinG

Дата 25.4.2008, 20:46 (ссылка)

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

Загрузка ...

Новичок

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

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

Эмм...короче вот что-то сделал, но сколько ни пытаюсь отладить не получается...помогите плиз(((

Код


//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop
#include <stack>
#include "stdio.h"
#include <fstream>
#include "conio.h"
//---------------------------------------------------------------------------

#pragma argsused
using namespace std;
class Tpoint{
public:

    int x,y;
    char bVisited;

    Tpoint(int _x,int _y){
    x=_x;y=_y;
   bVisited=1;
    }

    void print(){
    printf("[%d][%d]  ",x,y);
    }

};

stack  <class Tpoint> s[100];
stack  <class Tpoint> valt[100];
stack  <class Tpoint> *temp[100];

int left(Tpoint &A,Tpoint &B){
if ((A.x-1==B.x )&& (B.bVisited == 1)) {
 return 1;
}
else {return 0; }
}
int right(Tpoint &A,Tpoint &B){
if ((A.x+1==B.x) && (B.bVisited ==1)) {
 return 1;
}
else {return 0;   }
}
int hight(Tpoint &A,Tpoint &B){
if ((A.y-1==B.y )&& (B.bVisited ==1)) {
 return 1;
}
else {return 0;}
}
int floo(Tpoint &A,Tpoint &B){
if ((A.y+1==B.y) && (B.bVisited == 1)) {
 return 1;
}
else {return 0;}
}


int main(int argc, char* argv[]){

    bool lab[8][8]={
{1,1,1,1,1,1,0,0},
{1,0,0,0,1,0,0,0},
{0,1,1,1,1,0,0,0},
{0,1,0,0,0,1,0,1},
{0,1,1,1,1,1,0,1},
{0,1,0,0,0,0,0,1},
{0,1,1,1,0,0,0,1},
{0,0,0,1,1,1,1,1}};

int k=0;
Tpoint *object[100];
Tpoint *next;
next=new Tpoint(0,0);
Tpoint *object_n,*object_f;
//object_n=new Tpoint(0,0);
object_f=new Tpoint(3,7);
int a[120];
for(int i=0;i<120;i++){
a[i]=0;
}
for(int i=0;i<8;i++){
    for(int y=0;y<8;y++){
      if (lab[y][i]==1) {
           object[k]=new Tpoint(i,y);
           k++;
      }
    }
}




int i=0;
int m=0;
int g=0;
int j=0;
s->push(*object[0]) ;


next=object[0]; 

while(next->x!=object_f->x && next->y != object_f->y ){   
    j=0 ;
    while(j<k){
    int v;
        for(int p=0;p<k;p++)
        v=left(*next,*object[p])+right(*next,*object[p])+hight(*next,*object[p])+floo(*next,*object[p]);//ñìîòðèì â êàêóþ ñòîðîíó èäåò

        if(v==1){  
        object[j]->bVisited=0;
        s->push(*object[j]);
        a[m]++;
        next=object[j];
        j=k;
        }
        else{
            if (v>1) {        
            s->push(*object[j]);
            a[m]++;
            if(left(*next,*object[j])==1){object[j]->bVisited=0; s->push(*object[j]);next=object[j];  j=k;}
            if(right(*next,*object[j])==1){object[j]->bVisited=0; s->push(*object[j]);next=object[j];  j=k;}
            if(hight(*next,*object[j])==1){object[j]->bVisited=0; s->push(*object[j]);next=object[j];  j=k;}
            if(floo(*next,*object[j])==1){object[j]->bVisited=0; s->push(*object[j]);next=object[j];  j=k;}
            m=m+1;
            }
            else{
            g++;
            }
        }
        j++;
    }

        if(g==k){
            for(int l=0;l<a[m];l++){
                if(m!=0){
                s->pop();
                 m--;
                }
            }
      next=&s->top(); 
        }
}


    while(s->top().x==object[0]->x && s->top().y==object[0]->y){
    s->top().print();
    s->pop();
    }

  getch();
    return 0;

}

Это сообщение отредактировал(а) VerLinG - 25.4.2008, 22:05

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