VPF::[c++]зацикливается при прохождении по лабиринту

аНТ

Дата 7.3.2013, 10:12 (ссылка)

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

Загрузка ...

Новичок

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

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

Суть задачи: даны матрица NxM, даны 2 точки точка входа в лабиринт и выхода(пока отрубил,беру поиск с верхней точки), необходимо пройтись по лабиринту и найти путь до выхода, если выхода нет то соответствующее сообщение,  необязательно находить кратчайший путь, вывести эту же матрицу но с обозначением пройденного пути от начала к концу(любым символом),так то его надо в файл(но пока ладно),в данной матрице одна развилка беру пока без стека для проверки матрицу...
Беру для проверки матрицу:
        1,1,0,1,1,
        0,0,0,0,1,
        1,1,1,0,1,
        1,1,1,0,1,
        1,1,1,0,1

если pDown(); поднять выше то все работает, для этой матрицы

Код


#include <iostream>
#include <stack>
 
using namespace std;

//пока почти все переменные глобальные - позже в нормальный вид...

 //вводим матрицу 5х5
    int const mkY=5; 
    int const mkX=5;

//чтобы пока -1 не ставить везде
    int kY=mkY-1;
    int kX=mkX-1;

    int mat[mkY][mkX]={
        1,1,0,1,1,
        0,0,0,0,1,
        1,1,1,0,1,
        1,1,1,0,1,
        1,1,1,0,1

    };

    int posX = 0,
        posY = 0;

//Переменные
    //пустота
    //стена
    //позиция старта
    //позиция выхода

//Функции
void pLeft(void)//влево
{    
    if(mat[posY][posX-1]==0)
    {
        mat[posY][posX]=1;
        posX--;
    };
};

void pRight(void)//вправо
{
    if( (mat[posY][posX+1]==0) && (posX+1!=kX) ) 
    {
        mat[posY][posX]=1;
        posX++;
    };
};

void pDown(void)//вниз
{
    if(mat[posY+1][posX]==0)
    {
        mat[posY][posX]=1;
        posY++;        
    };
};

void pBottom(void)//вверх
{
    if(mat[posY-1][posX]==0)
    {
        mat[posY][posX]=1;
        posY--;        
    };
};

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


    //Выводит массив на экран
    for(int i = 0; i <= kY; i++)
        for(int j = 0; j<= kX; j++)
        {
            cout << mat[i][j] << ' ' ;
            if (j == kX) cout << endl;
        };

    cout << "- - - - - - -" << endl;

    int ST[2] = {0,1}, // 1.2 _start
        EN[2] = {4,2}; // 5.3 _end

//    int posX = 0,
//        posY = 0;

    posY = ST[0]; //позиция старта Строки  X
    posX = ST[1]; //позиция старта Столбца Y

    cout << "coordinats START: "<< posY << " " << posX << endl;
    cout << "coordinats END: "<< EN[0] << " " << EN[1] << endl;

    int kontr(0);

    posX=0;
    posY=0;
/* !!! нахождение точки выхода по углам, в ином случаи "Выхода нет!"  */
    //ищем точку входа сверху, 
    for (int j=0;j >= kX ;j++ )
        if (mat[0][j]==0){ 
    cout << 'z'<< posX <<endl;
            posX=j;
    cout << 'j'<< j <<endl;
        };

    for(int i=0; i <= kX;i++)
        if (mat[0][i]==0)posX=i;

//тестовые переменные
    int tm[10][10];//вместо стека
    int tt = 0;

    //mat[posY][posX]=1;
    while (kontr!=1)
    {
        //для проверки while, т.к условие в нём не работает!
          //if ((posY >= EN[0])&&(posX >= EN[1] ))kontr=1;

        if ((posY >= kY)&&(posX >= 1 ))kontr=1;
    
        cout << "Y=" << posY << " X=" << posX << endl;

        if(mat[posY][posX]==0)//текущая позиция ? = 0
        {


            //если после движения везде 1 
            if( ((mat[posY+1][posX]==1)&&(mat[posY-1][posX]==1)&&(mat[posY][posX+1]==1)&&(mat[posY][posX-1]==1))&&(tt>=1) )
            {
                mat[posY][posX]=1;
                posY = tm[0][0];
                posX = tm[0][1];
                mat[posY][posX]=0;
                cout<< "C>> " << "Y=" << posY << "X=" << posX <<endl;
                //tt --;
                tt = 0;
                //проверка не пустой ли стек, если да то прохода нет
            };
            
                

            //если после движения Д 0 
            if((posY<=kY)&&
                (
                ((mat[posY  ][posX+1]==0)&&(mat[posY  ][posX-1]==0))||//справа слева 
                ((mat[posY+1][posX  ]==0)&&(mat[posY  ][posX+1]==0))||//сверху справа
                ((mat[posY+1][posX  ]==0)&&(mat[posY-1][posX  ]==0))||//сверху снизу
                ((mat[posY+1][posX  ]==0)&&(mat[posY  ][posX-1]==0))||//сверху слева
                ((mat[posY  ][posX+1]==0)&&(mat[posY-1][posX  ]==0))||//справа снизу
                ((mat[posY  ][posX-1]==0)&&(mat[posY-1][posX  ]==0))  //слева снизу
                )        
              )
            {
                //сохранить позиции x y
                
                tm[0][0] = posY;
                tm[0][1] = posX;
                cout << "S<<" << " Y=" << posY << "X=" << posX <<endl;
                tt = 1;
                //сохраняем позицию в стек
                //tt ++;
            };
            pDown();//вниз
            pLeft();//влево
            pRight();//вправо

        };

    };

    cout << endl << "test END";

    getchar();
    return 1;
}

xvr

Дата 7.3.2013, 12:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

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

Цитата(аНТ @ 7.3.2013, 10:12

)

беру пока без стека для проверки матрицу...

Без стека зациклится на первой же развилке (что у вас и произошло)

Распечатайте координаты в процессе поиска - все увидите сами

аНТ

Дата 7.3.2013, 16:41 (ссылка)

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

Загрузка ...

Новичок

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

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

я и стараюсь выводить, что бы видно было где

Добавлено через 1 минуту и 57 секунд
попробую

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