2-d 미로에서 경로 찾기

Question

이 코드가 런타임 오류를주는 이유는 무엇입니까? 나는 그들의 존재가 음식에 도달하는 미로 내부의 경로인지 찾아 내려고 노력 중입니다 (2). 0은 장애물, 1은 경로, 2는 목적지를 나타냅니다. A는 미로와 출발점으로 i=3, j=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)로 시작점을 통과하고있다. 코드를 ideone : http://ideone.com/poF9um

나를 도와 주셔서 감사합니다. 나는 내 실수를 바로 잡았다. 다음은 업데이트 된 코드의 ideone 링크입니다. http://ideone.com/poF9um Thanks.

#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; 
} 

Answer 1

스택 오버플로가 원인입니다. 깊이 우선 검색은 방문한 위치를 표시하지 않으므로 동일한 위치가 여러 번 방문됩니다.

• (3, 2)에서 시작하여 왼쪽으로가보십시오.
• 이것은 (3, 1)으로 이동합니다.
• 경로가 (3, 1)으로 남아 있지 않으므로 올바르게 진행됩니다.
• 왼쪽으로 가려고 시도한 곳에서 (3, 2)으로 다시 이동합니다.
• 이것은 (3, 1)으로 이동합니다.
• 는

문제를 참조하십시오 ... 어떤 경로 (3, 1)의 왼쪽, 그래서 당신은 바로, 이동이? 이 문제를 해결하려면 방문한 장소의 다른 배열을 추가하고 검색을 계속하기 전에 확인하십시오. 이렇게하면 문제가 해결됩니다.

Answer 2

코드에서 무한 재귀 호출이 발생합니다. findPath (a, 3,2)를 실행하는 것으로 시작합니다. [3] [2] == 1이므로 코드는 findPath (a, 3,1)를 호출합니다. 이제 [3] [1] == 1부터 코드가 나중에 findPath (a, 3,2)에 다시 호출합니다 ... 등등 ... 메모리가 부족할 때까지/스택 오버플로 ...