如何找到一个迷宫最快路径（C语言） [英] How to find the fastest route in a maze (in C)
问题描述
迷宫被限定为方阵。
例如：
The maze is defined as a square matrix. For example:
int maze[N][N] =
{ { 1, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 1 },
{ 0, 1, 0, 0, 0, 1, 1 },
{ 0, 1, 1, 1, 0, 1, 1 },
{ 0, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1 } };
您可以步行只有在有一个1。
你可以采取的一个步骤向下，向上，左，右。
你开始在下跌时右上角的左上角和完成。
You can walk only where there's a 1. You can take a step down, up, left, right. You start at the top-left corner and finish at down-right corner.
输出应完成任何迷宫最基本的步骤。
我们可以假设有完成迷宫至少一种方式。
我已经编辑了code，我想我谈过了..但很显然，我失去了一些东西。
感谢您的帮助。
The output should be the minimum steps to finish any maze. We can assume there is at least one way to finish the maze. i've edited the code and i thought i covered everything.. but obviously i'm missing something. thanks for your help
int path_help(int maze[][N], int row, int col, int count)
{
int copy1[N][N], copy2[N][N], copy3[N][N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
copy1[i][j] = maze[i][j];
copy2[i][j] = maze[i][j];
copy3[i][j] = maze[i][j];
}
}
int a, b, c, d;
if (col == 0 || row == 0)
{
if (row == N - 1)
{
if (maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
else return N*N;
}
if (col == N - 1)
{
if (maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
else return N*N;
}
if (maze[row][col + 1] == 1 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col + 1, count + 1),path_help(maze, row + 1, col, count + 1));
}
if (maze[row][col + 1] == 0 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
if (maze[row + 1][col] == 0 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
else return N*N;
}
if (col == N - 1 || row == N - 1)
{
if (col == N - 1 && row == N - 1) return count;
if (row == N - 1)
{
if (maze[row - 1][col] == 1 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col + 1, count + 1), path_help(maze, row - 1, col, count + 1));
}
if (maze[row - 1][col] == 0 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
if (maze[row][col + 1] == 0 && maze[row - 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row - 1, col, count + 1);
}
else return N*N;
}
if (col == N - 1)
{
if (maze[row + 1][col] == 1 && maze[row][col - 1] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col - 1, count + 1), path_help(maze, row + 1, col, count + 1));
}
if (maze[row + 1][col] == 0 && maze[row][col - 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col - 1, count + 1);
}
if (maze[row][col - 1] == 0 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
else return N*N;
}
}
if (maze[row + 1][col] == 1)
{
maze[row][col] = 0;
a = path_help(maze, row + 1, col, count + 1);
}
else a = N*N;
if (maze[row - 1][col] == 1)
{
copy1[row][col] = 0;
b = path_help(copy1, row - 1, col, count + 1);
}
else b = N*N;
if (maze[row][col + 1] == 1)
{
copy2[row][col] = 0;
c = path_help(copy2, row, col + 1, count + 1);
}
else c = N*N;
if (maze[row][col - 1] == 1)
{
copy3[row][col] = 0;
d = path_help(copy3, row, col - 1, count + 1);
}
else d = N*N;
return min(min(a, b),min( c, d));
}
推荐答案
由于没有 0 作为不走，和 1 作为算法的距离。
Because there is no solution of Dijkstra's algorithm in the question linked by @Jackson, here is a modified algorithm adapted for this maze problem. I take the maze value 0 as no-go, and 1 as the distance for the algorithm.
看起来好像在嘶（）函数应该是递归的，但它不是，它是唯一的有，使4邻居能够以同样的方式进行检查。请注意，并非所有的路径如下：一个大迷宫，可能是O（不！）。此外，搜索不是的直接的到终点：遇到终点，算法的这些特点给它的美丽
It looks as though the neigh() function should be recursive, but it is not, it is only there so that 4 neighbours can be examined in the same way. Note that not every path is followed: for a large maze that could be O(no!). Also that the search is not directed to the end point: the end point is encountered, and these features of the algorithm give it its beauty.
#include <stdio.h>
#include <stdio.h>
#include <limits.h>
#define MSIZE 7 // matrix/maze dims
enum ntype { virgin, listed, visited }; // for status field
typedef struct {
int x; // grid position of node
int y; // grid position of node
int value; // 0 or 1 as defined in maze[][]
int dist; // distance from start node
int status; // enum as above
} node_t;
int maze[MSIZE][MSIZE] = // maze definition
{ { 1, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 1 },
{ 0, 1, 0, 0, 0, 1, 1 },
{ 0, 1, 1, 1, 0, 1, 1 },
{ 0, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1 } };
node_t node [MSIZE][MSIZE]; // working array
node_t *list[MSIZE*MSIZE]; // array of current node pointers
int listlen; // num elements in list[]
void neigh(node_t *cptr, int dx, int dy)
// examine one neighbour of node cptr, offset by dx,dy
{
node_t *nptr; // pointer to neighbour
int dist; // accumulated distance from start
int x = cptr->x + dx; // work out neighbour coords
int y = cptr->y + dy; // work out neighbour coords
if (x < 0 || x >= MSIZE || y < 0 || y >= MSIZE)
return; // failed edge test
nptr = &node[y][x]; // point to neighbour
if (nptr->value == 0) // no-go node
return;
if (nptr->status == visited) // do no re-visit
return;
dist = cptr->dist + nptr->value; // accumulate distance from start
if (dist < nptr->dist) // if it's less than what was known...
nptr->dist = dist; // ...update with the new distance
if (nptr->status == virgin) { // if it's never been seen...
list[listlen++] = nptr; // ... neighbour to list
nptr->status = listed; // and set its status
}
}
int main(void)
{
int i, j, smallest, smallind;
node_t *cptr, *eptr;
// init the struct array
for (j=0; j<MSIZE; j++) {
for (i=0; i<MSIZE; i++) {
cptr = &node[j][i]; // pointer to the array element
cptr->value = maze[j][i]; // the maze definition
cptr->x = i; // self's position
cptr->y = j; // self's position
cptr->dist = INT_MAX; // distance from start (unknown)
cptr->status = virgin; // never examined
}
}
eptr = &node[MSIZE-1][MSIZE-1]; // pointer to end node
cptr = &node[0][0]; // pointer to start node
cptr->dist = 0; // distance of start node from itself!
// main loop
while (cptr != eptr) { // until we reach the target node
cptr->status = visited; // we've been here now
neigh(cptr, 0, -1); // examine node above
neigh(cptr, -1, 0); // examine node on left
neigh(cptr, 1, 0); // examine node on right
neigh(cptr, 0, 1); // examine node below
// find smallest distance of nodes in list[] (won't include virgins)
smallest = INT_MAX;
smallind = -1; // set invalid marker index
for (i=0; i<listlen; i++) {
if (smallest > list[i]->dist) { // compare distance with smallest
smallest = list[i]->dist; // remembers the smallest
smallind = i; // remembers the list index of smallest
}
}
// take smallest for next time and remove from list
if(smallind < 0) { // -1 was the "marker"
printf("No route found\n");
return 1;
}
cptr = list[smallind]; // smallest becomes current node
if (listlen) // replace in list with last element...
list[smallind] = list[--listlen];// ... and reduce list length
} // now examine this node
printf("Distance = %d\n", eptr->dist); // show the distance of the end node
return 0;
}
程序输出：
Distance = 12
修改这个算法本身在链接描述，如果它打破了有肯定是其他的解释可用。我已经加入更多评论到code。
EDIT The algorithm itself is described in the link, if it breaks there are sure to be other explanations available. I have added more comments to the code.
我用3阵列，迷宫[] [] 是像你这样一个简单的迷宫定义。然后节点[] [] 是结构占据着运行时数据的数组。我可以跟迷宫定义直接initiliased这一点，但由于这种来自于程序有一个矩阵大小，并与从文件中读取数据更大的矩阵硬codeD的测试数据，我离开它，因为它是。
I use 3 arrays, maze[][] is a simple maze definition like yours. Then node[][] is an array of struct which hold runtime data. I could have initiliased this with the maze definition directly, but because the program this came from had hard-coded test data of one matrix size, and a bigger matrix with data read from file, I left it as it was.
第三排列表[] 是一个指针到节点[] [] 元素的数组。这就是为什么节点[] [] 元素中包含 X，Y 的结构本身的坐标：让我可以知道单从指针的位置。我可以用一维数组迷宫工作过，当我可以存储在单个指数列表[] ，如果是这种并发症不会是必要的。但是我用了2-D阵列，只是因为它觉得漂亮。
The third array list[] is an array of pointers to the node[][] elements. This is why node[][] elements contain the x,y coordinates within the struct itself: so that I can know the position from the pointer alone. I could have worked with a 1-D maze array, when I could have stored a single index in list[], if so this complication would not have been necessary. But I used a 2-D array, just because it felt "nicer".
我很舒服与指针的工作。在第一循环嵌套对的main（）为首 //初始化的结构阵列我做的第一件事就是做一个指针，用于设置结构领域的应用，因为我发现重复使用数组索引笨拙。所以我写例如 cptr-＆GT; X = 1; 具有相同意向的节点[J] [I] .X = I; 。
I am comfortable working with pointers. In the first nested loop pair in main() headed // init the struct array the first thing I do is to make a pointer, for use in setting the struct fields, because I find the repeated use of array indexing clumsy. So I write for example cptr->x = i; which has the same intent as node[j][i].x = i;.
这篇关于如何找到一个迷宫最快路径（C语言）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
