如何在迷宫中找到最快的路线（在C中）
迷宫被定义为方阵。 例如：
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的地方行走。你可以向下，向上，向左，向右走。 你从左上角开始，在右下角完成。
输出应该是完成任何迷宫的最小步骤。 我们可以假设至少有一种方法可以完成迷宫。 我编辑了代码，我认为我涵盖了一切……但显然我错过了一些东西。 谢谢你的帮助
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));
}
因为在@Jackson链接的问题中没有Dijkstra算法的解决方案，所以这里有一个适用于这个迷宫问题的修改算法。 我将迷宫值0视为禁止，并将1作为算法的距离。
看起来neigh()函数应该是递归的，但事实并非如此，只有那样才能以相同的方式检查4个邻居。 请注意，并非所有路径都遵循：对于可能是O（不！）的大型迷宫。 此外，搜索不是针对终点：遇到终点，算法的这些特征赋予其美感。
#include #include #include #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; jvalue = 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 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
编辑算法本身在链接中描述，如果它中断，肯定会有其他解释。 我在代码中添加了更多注释。
我使用3个数组， maze[][]是一个像你一样简单的迷宫定义。 然后node[][]是一个包含运行时数据的struct数组。 我可以直接使用迷宫定义来启动它，但是因为这个来自的程序具有一个矩阵大小的硬编码测试数据，以及从文件读取数据的更大矩阵，所以我保持原样。
第三个数组list[]是指向node[][]元素的指针数组。 这就是node[][]元素在结构本身中包含x,y坐标的原因：这样我就能从指针中知道位置。 我可以使用一维迷宫arrays，当我可以在list[]存储单个索引时，如果是这样，这种复杂性就没有必要了。 但我使用了二维arrays，只是因为它感觉“更好”。
我很乐意使用指针。 在main()的第一个嵌套循环对// init the struct array ，我做的第一件事是创建一个指针，用于设置struct字段，因为我发现重复使用数组索引笨拙。 所以我写的例如cptr->x = i; 其意图与node[j][i].x = i; 。
从根本上说，这是一个搜索问题。 有很多关于如何解决的好文章，所以我将谈谈你需要考虑的一些更好的观点。
由于您指定了最短路径，而不仅仅是“非常好”的路径，因此您需要检查每条可能的路径。 深度优先搜索将是我的建议。
最明显的是，这是没有重用的搜索。 最短路径不包含任何循环或光标将返回到已经存在的位置的任何情况。 这使搜索区域合理。
如果运行时不是问题，您可以编写一个函数来尝试每个可能的路径，并返回最小值。
int path_helper(int maze[][N],int height, int width, int row, int col){ if(row==height-1 && col == width-1) return 0; if(maze[row][col]==0) return height*width; if(col<0 || row<0 || row>=height || col>=width) return height*width; maze[row][col]=0; int maze2[7][7]={{0}}; for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++) maze2[j][i]=maze[j][i]; } return min(min(path_helper(maze2,height,width,row+1,col), path_helper(maze2,height,width,row-1,col)), min(path_helper(maze2,height,width,row,col+1),path_helper(maze2,height,width,row,col-1)))+1; }
这很难看，但它应该可以解决问题