미로에서 최소 경로 찾기

Question

그래서 미로에서 최소 경로의 길이를 찾는 코드를 작성해야합니다.

미로는 NxN 행렬이며 시작점은 (0,0)이고 끝점은 (N, N)입니다. 셀에 1이 들어 있으면 0을 통과 할 수 있습니다. 미로에는 해결책이있을 수도 있고 없을 수도 있습니다.

이 내 코드는이 솔루션이 가정, 지금까지입니다 :

int path_finder(int maze[][N], int n, int row, int col) // n equal N 
{ 
int i, j, pth; 

if (row == n-1 && col == n-1) // Return 0 if I get to goal 
    return 0; 

if (col < 0 || row < 0 || row > n-1 || col > n-1) // Same 
    return n*n; 

if (maze[row][col] == 0) // Return big number to make sure it doesn't count 
    return n*n; 

maze[row][col] = 0; 

pth = min(1+path_finder(maze,n, row+1, col), // Assume I already know the path 
      1+path_finder(maze,n, row-1, col), // from the next starting point 
      1+path_finder(maze,n, row, col+1), // just add 1 to it 
      1+path_finder(maze,n, row, col-1) ); 

maze[row][col] = 1; 

return pth; 
} 

을 나는 항상 얻을 N^2 + 1, 나는 단지 내가 최소 기능에 보내는 마지막 인자를 계산 가정하지만 그것을 고치는 법을 모른다?

Answer 1

문제가 실용적이면 A *를 사용하십시오. 가까운 최적의 distractor 경로가되도록 문제가 고안 경우

https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/astar.c

. 휴리스틱을 제거하고 포괄적 인 검색을 수행하도록 함수를 수정하십시오.