Traverse maze and Depth First Search

Question

오늘 DFS를 배웠고 오늘 밤 연습을했습니다.

내 프로그램에서 문제가 발생했습니다.

http://codepad.org/quq5FcwR

void dfs(int x,int y){ 
    if(maze[x][y]==0) maze[x][y]=2; 
    if(maze[8][8]==2){ 
    flag=true; 
    return; 
    } 
    if(maze[x+1][y]==0 && x+1<9){ 
    maze[x][y]=2; 
    maze[x+1][y]=2; 
    dfs(x+1,y); 
    if(f lag==false){ 
     maze[x+1][y]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x][y+1]==0 && y+1<9){ 
    maze[x][y]=2; 
    maze[x][y+1]=2; 
    dfs(x,y+1);         
    if(flag==false){ 
     maze[x][y+1]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x-1][y]==0 && x-1>0){ 
    maze[x][y]=2; 
    maze[x-1][y]=2; 
    dfs(x-1,y);         
    if(flag==false){ 
     maze[x-1][y]=0; 
     maze[x][y]=0; 
    } 
    } 
    else if(maze[x][y-1]==0 && y-1>0){ 
    maze[x][y]=2; 
    maze[x][y-1]=2; 
    dfs(x,y-1);         
    if(flag==false){ 
     maze[x][y-1]=0; 
     maze[x][y]=0; 
    } 
    } 
    return; 
} 

1. 링크

내가 쓰는 프로그램입니다,하지만 난 최단 경로를 찾는 방법을 모르겠어요.

2. 스택을 사용하여 수행하는 방법에 대한 조언을 할 수 있습니까? 재귀 적으로 만 사용합니다. 위키를 본 적이 있지만 스택 사용 방법을 이해할 수 없습니다 (예 : 1 사용 방법 . -D 배열은 2 차원 배열에 대한 포인트를 기록, 난 당신이 내 문제를 읽는 시간을 보내고 위해

Answer 1

여러 지점이 경우에 대한 언급이 있습니다

감사) 그래서 그것에 대해 혼란 스러워요 :

1) 가장 간단한 스택은 재귀 스택이며 이미 코드를보고있는 것 같습니다. 나는. dfs() 함수를 호출 할 때마다 모든 변수가 스택에 저장됩니다. 귀하의 경우에는 x와 y를 호출하면 나중에 반환하기 위해 저장됩니다. 나는. 일단 dfs() x에서 돌아 오면 y는 당신이 전화하기 전에 가지고 있던 가치와 같을 것입니다.

2) 돌아 오기 전에 마지막 변경 사항을 실행 취소해야합니다. 함수의 시작 부분에 maze[x][y]=2을 설정하십시오. 반환하기 전에이 공간을 막 다른 길로 인도 할 수 있으므로이 작업을 취소해야합니다.

3) DFS를 사용하면 메모리 사용량이 적은 경로를 찾을 수 있습니다. 그러나 DFS에 의해 발견 된 경로는 최단 경로가 아닐 수 있습니다. 가장 짧은 경로를 찾을 수 있지만 메모리 사용량이 훨씬 더 많은 BFS라는 다른 알고리즘이 있습니다. 그런 다음 최단 경로를 찾고 반복적 인 DFS가 발생하며 메모리 소비는 적지 만 시간이 오래 걸립니다. 원하는 것을 결정한 다음 알고리즘을 선택해야합니다.

Answer 2

DFS보다 최단 경로를 찾기 위해 BFS를 수행하는 것이 좋습니다.

2 차원 미로에서 한 지점을 나타내는 데 2 ​​개의 1 차원 배열을 사용할 수 있습니다.

2 차원 미로를 통과하기 위해 대기열로 xq [maxlength], yq [maxlength]를 사용했습니다.

당신은, 당신이 큐 포인트 (XP, YP)를 취득하고자 할 때

xq[back] = xi; 
yq[back] = yi; 
back++; 

을 큐에 새 위치 (XI, 이순신)를 삽입 할 때

xp = xq[front]; 
yp = yq[front]; 
front++; 

처음에는 앞면과 뒷면이 0이됩니다. 대기열이 완료되고이를 사용하여 BFS를 수행 할 수 있습니다.