“波算法"(Wave Algorithm)(基于李的算法)在C语言中 [英] "Wave Algorithm" (based in Lee's Algorithm) in C
问题描述
我正在编写从A点到B点的最短程序计算.我有一个具有值的地图(矩阵):
I'm writing a program calculation the shortest way from point A to point B. I have a map (matrix) with values:
- 0是障碍物(墙壁，无法通过)；
- 1种自由方式(您可以通过)；
- 11是点A(起点)；
- 22是B点(终点).
我已经阅读了几篇文章，它应该如何工作，并试图实现我自己的版本，但是堆积如山.
I've read a few articles how it should work and tried to realize my own version but got stacked.
在下面的代码中，我声明了2个数组:一个Map数组和一个运行已访问点的程序时访问过"已更改的数组.
In the code below I declare 2 arrays: an array with Map and changed array "visited" while running program demonstrating visited points.
我在4个方向(不是对角线)上检查单元格是1还是0.如果它是1(可以通过)，我将计数器增加1.条件.
I check the cells in 4 directions (not diagonals) for 1 or 0. If it's 1 (possible to pass), I increase the counter for 1. For do not count the previous cell I'm trying to avoid it by the condition.
结果，我想看到带有几行的已访问"矩阵，该矩阵显示了到达点B(1、2、3，... 15)的方式.
As a result I wanna see "visited" matrix with a few lines which shows the way to reach to the point B (1, 2, 3, ... 15).
现在我的地图看起来不正确，甚至没有关闭.
Right now my map doesn't look like correct, not even close.
我在算法中遗漏了什么，应该考虑什么以及如何修复程序?
What have I missed in my algorithm, what should I take into account and how to fix my program?
谢谢.
P.S.我编写了一些函数来实现一个具有0值的新数组，可以自由计数单元格并打印数组.
P.S. I wrote a few functions implementing a new array with 0 values, counting free to go cells and printing arrays.
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个单元格
Here the shortest way is always 15 cells
推荐答案
在 main 函数的嵌套循环中，表达式((i> = 0)&&(i< WIDTH))&&((j> = 0)&&(j< HEIGHT))将始终为true.
In the nested loops in the main function, the expression ((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT)) will always be true.
这意味着您将超出数组的范围.
That means you will go out of bounds of your arrays.
我建议您检查 i 的值，例如 if(map [i + 1] [j] == 1).也许像
I suggest you check value of i as part of doing e.g. if (map[i + 1][j] == 1). Perhaps something like
if (i < WIDTH - 1 && map[i + 1][j] == 1) { ... }
如果您在其他地方也执行类似操作(例如，当执行 i-1 检查 i> 0 时)，则不应超出范围并具有未定义的行为.
If you do it similar for the other places as well (for when you do i - 1 check i > 0) then you should not go out of bounds and have undefined behavior.
与上述检查类似的另一种可能性是，对范围内的 i (或 j )进行一次检查，然后进行您现在所拥有的检查.像
Another possibility that's similar to the above check is to have one check for i (or j) being in range and then do the check you have now. Sonething like
if (i < WIDTH - 1)
{
if (map[i + 1][j] == 1) { ... }
if (map[i + 1][j] == 0) { ... }
}
这篇关于“波算法"(Wave Algorithm)(基于李的算法)在C语言中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
