Cの迷路で最小限の経路を見つける

Question

だから、迷路内の最小経路の長さを見つけるコードを作る必要があります。

迷路はNxN行列で、開始点は（0,0）、終了点は（N、N）です。セルには1が含まれています。迷路には解決策がある場合とない場合があります。

これは私のコードは、それが解決策があると仮定すると、これまでのところです：

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、私は、それだけで私はmin関数に送る最後の引数を数えると仮定けどそれを修正する方法を知らない？

Answer 1

問題が実用的な場合は、A *を使用してください。

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

ほぼ最適な伸延器のパスがあるように、問題が不自然である場合。ヒューリスティックを取り出すために関数を変更し、網羅的な検索を行います。