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

Почему этот код выдает ошибку во время выполнения. Я пытаюсь найти, существует ли путь внутри лабиринта, чтобы добраться до еды (2). 0 означает препятствие, 1 — путь, а 2 — пункт назначения.

        `{0,1,1,0,0},
         {1,0,1,1,1},
         {0,0,0,0,0},
         {0,1,1,1,1},
         {0,0,1,1,0},
         {1,0,1,1,2}`

Я передаю начальную точку как findpath(a,3,2), где a — лабиринт, а i=3, j=2 — как начальную точку. Код на ideone: http://ideone.com/poF9um

Спасибо, ребята, что помогли мне. Я исправил свою ошибку. Вот ссылка на обновленный код ideone: http://ideone.com/poF9um Спасибо.

#include <iostream>
using namespace std;

/*int insideMaze(int x, int y){
if(x>=6 || y >=5 || x<0 || y< 0)
{
    return 0;
}
return 1;
}*/
bool findPath(int a[6][5], int n1, int m1){
if(n1>=6 || m1 >=5 || n1<0 || m1<0){
    return false;
}

if(a[n1][m1] == 0){
    return false;
}
if(a[n1][m1]==2){
    return true;
}
//a[n1][m1] = 4;
if(findPath(a,n1-1,m1)==true){
    return true;
}
if(findPath(a,n1,m1-1)==true){
    return true;
}
if(findPath(a,n1+1,m1)==true){
    return true;
}
if(findPath(a,n1,m1+1)==true){
    return true;
}

return false;
}

int main() {
// your code goes here
//int a[10][10];
int a[6][5] = {
         {0,1,1,0,0},
         {1,0,1,1,1},
         {0,0,0,0,0},
         {0,1,1,1,1},
         {0,0,1,1,0},
         {1,0,1,1,2}
        };
if(findPath(a,3,2)){
    cout<<"Path Found";
}

return 0;
}

person nitte93user3232918    schedule 31.01.2015    source источник
comment
Заставьте его печатать места, которые он посещает, и вы увидите, в чем проблема.   -  person interjay    schedule 31.01.2015


Ответы (2)


Проблема вызвана переполнением стека. Ваш поиск в глубину не отмечает места, которые он посещает, поэтому одно и то же место будет посещено несколько раз.

  • Вы начинаете с (3, 2) и пытаетесь пойти налево.
  • Это приведет вас к (3, 1).
  • От (3, 1) пути слева нет, так что идите направо.
  • Это вернет вас к (3, 2), откуда вы попытаетесь пойти налево.
  • Это приведет вас к (3, 1).
  • От (3, 1) пути слева нет, так что идите направо...

Видите проблему? Чтобы это исправить, добавьте еще один массив посещенных вами спотов и проверьте его, прежде чем продолжить поиск. Это решит проблему.

person Sergey Kalinichenko    schedule 31.01.2015

Я предполагаю, что код вызывает бесконечные рекурсивные вызовы. Вы начинаете с выполнения findPath(a,3,2). Поскольку a[3][2]==1, код вызовет findPath(a,3,1). Теперь, поскольку a[3][1]==1, код позже снова вызовет findPath(a,3,2) снова... И так далее... Пока у вас не закончится память/переполнение стека.. .

person Noamiko    schedule 31.01.2015