c - C语言中的"Wave Algorithm"(基于Lee算法)

Question

我正在编写一个程序计算从A点到B点的最短路线。 我有一个带有值的 map (矩阵):

• 0是封锁(墙，无法通过)；
• 1 是免费路(可以通过)；
• 11是A点(起点)；
• 22 是 B 点(终点)。

我读过几篇关于它应该如何工作的文章，并尝试实现我自己的版本，但遇到了困难。

在下面的代码中，我声明了 2 个数组:一个带有 Map 的数组，并在运行演示访问点的程序时更改了“visited”数组。

我检查 4 个方向(不是对角线)的单元格是否为 1 或 0。如果是 1(可能通过)，我会增加计数器 1。为了不计算前一个单元格，我试图通过以下方式避免它:条件。

因此，我想看到“访问过”的矩阵，其中有几行显示了到达点 B(1, 2, 3, ... 15)的方式。

现在我的 map 看起来不正确，甚至不接近。

我的算法遗漏了什么，我应该考虑什么以及如何修复我的程序？

谢谢。

附注我编写了一些函数来实现一个值为 0 的新数组、计算自由单元格并打印数组。

main.c:

    #include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

#define WIDTH 8
#define HEIGHT 8

int mapZero(int map[WIDTH][WIDTH]);
int mapPrint(int map[WIDTH][HEIGHT]);
int mapInit(int map[WIDTH][WIDTH]);
int findFreeToGoCells(int map[WIDTH][WIDTH]);

int main(int argc, char * argv[])
{
    short int prevPosition;
    short int currPosition;
    short int nextPosition;
    short int lastPosition;

    int visited[WIDTH][HEIGHT];

    unsigned int count;
    unsigned int max;

    mapZero(visited);

    int map[WIDTH][HEIGHT] =
    {
        { 11, 1, 1, 1, 1, 0, 0, 1 },
        { 0, 1, 1, 1, 1, 1, 0, 1 },
        { 0, 0, 1, 0, 1, 1, 1, 0 },
        { 1, 0, 1, 1, 1, 0, 1, 1 },
        { 0, 0, 0, 1, 0, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 0, 0, 1 },
        { 0, 0, 0, 0, 1, 0, 0, 1 },
        { 0, 1, 1, 1, 1, 1, 1, 22 },

    };

    printf("Matrix of zeroed-visited cells:\n\n");
    mapPrint(visited);

    printf("Matrix of the map:\n\n");
    mapPrint(map);

    printf("Ways: %d\n", findFreeToGoCells(map));

    prevPosition = map[0][0];
    currPosition = 0;

    count = 0;
    max = WIDTH * HEIGHT;

    for (int i = 0; i < WIDTH; ++i)
    {
        for (int j = 0; j < HEIGHT; ++j)
        {
            if (((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT)))
            {
                // [i + 1][j] 
                if (map[i + 1][j] == 1)
                {
                    map[i][j] = prevPosition;
                    if (prevPosition)
                        visited[i + 1][j] = count++;

                }
                if (map[i + 1][j] == 0)
                {
                    visited[i + 1][j] = map[i + 1][j];
                }

                // [i - 1][j]
                if (map[i - 1][j] == 1)
                {
                    map[i][j] = prevPosition;
                    if (prevPosition)
                        visited[i - 1][j] = count++;
                }
                if (map[i - 1][j] == 0)
                {
                    visited[i - 1][j] = map[i - 1][j];
                }

                // [i][j + 1]
                if (map[i][j + 1] == 1)
                {
                    map[i][j] = prevPosition;
                    if (prevPosition)
                        visited[i][j + 1] = count++;
                }
                if (map[i][j + 1] == 0)
                {
                    visited[i][j + 1] = map[i][j + 1];
                }

                // [i][j - 1]
                if (map[i][j - 1] == 1)
                {
                    map[i][j] = prevPosition;
                    visited[i][j - 1] = map[i][j - 1];
                    if (prevPosition)
                        visited[i][j - 1] = count++;
                }
                if (map[i][j - 1] == 0)
                {
                    visited[i][j - 1] = map[i][j - 1];
                }

            } // map borders check (finished)
              //count++;
        }
    }

    printf("count: %d\n", count);

    if (count > 1000)
    {
        printf("The way couldn't be found\n");
    }
    else
    {
        printf("Matrix of visited cells:\n\n");
        mapPrint(visited);
        //printf("Short way: %d\n", findShortWay(map[7][7]));
    }
    printf("Ways: %d\n", findFreeToGoCells(visited));

    system("pause");
    return 0;
}

int mapZero(int map[WIDTH][WIDTH])
{
    for (int i = 0; i < WIDTH; ++i)
    {
        for (int j = 0; j < HEIGHT; ++j)
        {
            map[i][j] = 0;
        }
    }
}

int mapPrint(int map[WIDTH][HEIGHT])
{
    for (int i = 0; i < WIDTH; ++i)
    {
        for (int j = 0; j < HEIGHT; ++j)
        {
            printf("%2d  ", map[i][j]);
        }
        printf("\n\n");
    }
    printf("\n");
    return 0;
}

int findFreeToGoCells(int map[WIDTH][WIDTH])
{
    int count = 0;
    for (int i = 0; i < WIDTH; ++i)
    {
        for (int j = 0; j < HEIGHT; ++j)
        {
            if (map[i][j] == 1 || map[i][j] == 99) count++;
        }
    }
    return count;
}

这里最短路线始终是 15 个单元格

Answer 1

在main中的嵌套循环中函数，表达式 ((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT)) 永远是真的。

这意味着您将超出数组的范围。

我建议您检查 i 的值作为做事的一部分，例如if (map[i + 1][j] == 1) 。也许类似

if (i < WIDTH - 1 && map[i + 1][j] == 1) { ... }

如果您对其他地方也执行类似的操作(当您执行 i - 1 检查 i > 0 时)，那么您不应该越界并出现未定义的行为。

与上述检查类似的另一种可能性是对 i 进行一次检查(或 j )在范围内，然后进行您现在进行的检查。类似的东西

if (i < WIDTH - 1)
{
    if (map[i + 1][j] == 1) { ... }

    if (map[i + 1][j] == 0) { ... }
}