c - 使用 C 实现二维数组中的最短路径

Question

我想找到一条从 (0,0) 到 (6,6) 的最短路径，但我不知道如何使用 C 来实现。-1 是我可以走的路，-2 是路我不能去。 0是起点，-3是终点。请帮忙..

#include<stdio.h>

#define VERTICES 7

int maze[VERTICES][VERTICES] = {
{  0, -2, -1, -1, -1, -1, -1 },
{ -1, -2, -1, -2, -2, -2, -2 },
{ -1, -1, -1, -1, -1, -1, -1 },
{ -1, -2, -2, -2, -2, -2, -1 },
{ -1, -2, -1, -1, -1, -2, -1 },
{ -1, -2, -1, -2, -2, -2, -1 },
{ -1, -1, -1, -2, -1, -1, -3 } };

int A[VERTICES][VERTICES];

printA(int n)
{
int i, j;
printf("===============================\n");
for (i = 0; i < n; i++){
    for (j = 0; j < n; j++)
        printf("%3d", A[i][j]);
    printf("\n");
}
printf("===============================\n");
}
void solve(int n)
{
int i, j, k=0;
for (i = 0; i<n; i++)
    for (j = 0; j<n; j++)
        A[i][j] = maze[i][j];

while (1)
{
    for (i = 0; i < n; i++)
    {   
        for (j = 0; j < n; j++)
            if (A[i][j] == k)
            {
                if (0 <= i + 1 < n && 0 <= j < n && A[i + 1][j] == -1)
                    A[i + 1][j] = k + 1;
                if (0 <= i - 1 < n && 0 <= j < n && A[i - 1][j] == -1)
                    A[i - 1][j] = k + 1;
                if (0 <= i < n && 0 <= j + 1 < n && A[i][j + 1] == -1)
                    A[i][j + 1] = k + 1;
                if (0 <= i < n && 0 <= j - 1 < n && A[i][j - 1] == -1)
                    A[i][j - 1] = k + 1;
                if (A[i][j] == -3)
                    break;
            }
    }
    k++;
}
printf("%d\n", k);
printA(VERTICES);
}

main()
{
solve(VERTICES);
}

Answer 1

我知道，这应该是一个赞扬，但我没有足够的声誉..无论如何:

您还可以寻找 a*(a-star)算法来解决您的问题，这里有大量的实现和描述，例如:

http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/

http://www.codeproject.com/Articles/9880/Very-simple-A-algorithm-implementation

heyes-jones.com/astar.php