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

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 *.

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

Если проблема ухитрился так, что есть почти оптимальные пути отвлекающих. Измените функцию, чтобы вывести эвристику и выполните исчерпывающий поиск.