我们大家在小时候可能都玩过 找路线逃出迷宫 这样的小游戏通常的玩法一般是一开始顺着入口往后面走, 遇到岔路口, 就选择其中一条路往后走, 走到此路无路可走的时候 , 就再退回到岔路口, 然后再去选另外的一条路走, 每次走到此条路不通时就返回到上一个岔路口另选一条路走 ...... 经历这般 摸爬滚打之后, 最后才可能走到出口这里编程解决迷宫的思路同样如此
首先, 还是先来做准备工作, 定义一个全局的二维数组表示迷宫一个结构体变量表示坐标, 如下
<1> 先来解决简单的这种迷宫 (没有回路), 如下:
用递归的思路, 容易想到 : 从入口点开始, 在与它相邻各个方向中找出一可通的位置, 然后跳至该处并把此位置的值置为 2, 然后重复以上操作, 划分子问题, 当最后到达规定的出口时停止算法
代码如下:
- #pragma once
- #include <string.h>
- #define N 7
- int maze[N][N]={
- {0,0,0,0,0,0,0},
- {0,1,1,1,1,0,0},
- {0,1,0,0,0,0,0},
- {0,1,0,0,0,0,0},
- {0,1,1,1,1,0,0},
- {0,1,0,0,1,1,1},
- {0,1,0,0,0,0,0},
- };
- typedef struct Pos
- {
- int _col;
- int _row;
- }Pos;
- void PrintMaze(int arr[][N])
- {
- assert(arr);
- for(size_t i = 0; i< N; ++i)
- {
- for(size_t j = 0; j < N; ++j)
- printf("-", maze[i][j]);
- printf("\n");
- }
- printf("\n");
- }
- int IsAccess(Pos cur, Pos next)
- {
- if(maze[next._row][next._col] == 1
- && 0<= next._row && next._row < N
- && 0<= next._col && next._col < N)
- {
- return 1;
- }
- return 0;
- }
- void GetPath(Pos cur)
- {
- Pos next = cur;
- if(cur._col == N -1) // 找到出口
- {
- printf("出口:<%d, %d>\n", cur._row, cur._col);
- //return ;
- }
- maze[cur._row][cur._col] = 2;
- // 右
- next = cur;
- next._col+= 1;
- if(IsAccess(cur, next))
- GetPath(next);
- // 向上走
- next = cur;
- next._row-= 1;
- if(IsAccess(cur, next))
- GetPath(next);
- // 向下
- next = cur;
- next._row+= 1;
- if(IsAccess(cur, next))
- GetPath(next);
- // 左
- next = cur;
- next._col-= 1;
- if(IsAccess(cur, next))
- GetPath(next);
- }
上面代码可以找出可通的路线, 但是针对带回路的路线就会出现问题, 同时 此种方式不能找出最短的那条路线, 并不理想
继续往下优化 ~_~ ...
<2 > 带环的多条线路迷宫, 选择路径最短的一条线路
有一种比较巧妙的办法: 改变记录迷宫线路的方式来实现
思路: 改变记录走过位置的标记方式当前坐标位置的标记值是上一个位置的标记值加 1
得到;(假如某个位置走过了, 被标记为了 4, 那么走过的下一个位置就将其标记为 5... )
与此同时, 这样的记录方式还有一好处就是间接的表示了一条路径的长度
由于改变了标记的方式, 判断下个位置是否可通的条件做相应改变
判断可通条件: 当前坐标的标记值 < 下一个坐标处的标记值 或者 下一个坐标标记值为 1
注意: 由于标记为 1 的坐标也表示可通, 所以初始时入口处坐标不妨从 2 开始标记
代码如下:
- #include "Stack.h" // 上次实现的栈头文件
- int IsAccessInShortPath(Pos cur, Pos next)
- {
- if(( maze[cur._row][cur._col] < maze[next._row][next._col] // 当前坐标的标记值 < 下一个坐标处的标记值
- || maze[next._row][next._col] == 1)
- && 0<= next._row && next._row < N
- && 0<= next._col && next._col < N )
- {
- return 1;
- }
- return 0;
- }
- Stack shortPath; // 用一个全局的栈保存最短路径
- void GetShortPath(Pos cur, Stack* pPath)
- {
- Pos next = cur;
- if(StackEmpty(pPath) == 0) // 初始入口位置 记为 2
- maze[cur._row][cur._col] = 2;
- else
- {
- Pos prev = StackTop(pPath); // 当前位置标记值 为上一个位置标记值 + 1
- maze[cur._row][cur._col] = maze[prev._row][prev._col] + 1;
- }
- StackPush(pPath, cur);
- if(cur._col == N -1) // 找到出口
- {
- printf("出口:<%d, %d>\n", cur._row, cur._col);
- // 每找到一条路线就和 shortPath 里的路线比较长短
- // 找到的路线更短, 刷新 shortPath
- if(StackSize(pPath) < StackSize(&shortPath)
- || StackEmpty(&shortPath) == 0) // 初始 shortPath 为空, 需要刷新
- {
- // 不能直接 shortPath._array = pPath->_array 这样赋值
- //shortPath._array = pPath->_array;
- //shortPath._end = pPath->_top;
- //shortPath._top = pPath->_top;
- if(shortPath._array) // 刷新 shortPath, 由于每次额外开辟空间来保存较短路径
- free(shortPath._array); // 需要释放上一次开辟空间
- shortPath._array = (DataType*)malloc(sizeof(DataType)* pPath->_top);
- memcpy(shortPath._array, pPath->_array, sizeof(DataType) * pPath->_top);
- shortPath._end = pPath->_top;
- shortPath._top = pPath->_top;
- }
- }
- // 向上走
- next = cur;
- next._row-= 1;
- if(IsAccessInShortPath(cur, next))
- GetShortPath(next, pPath);
- // 向下
- next = cur;
- next._row+= 1;
- if(IsAccessInShortPath(cur, next))
- GetShortPath(next, pPath);
- // 左
- next = cur;
- next._col-= 1;
- if(IsAccessInShortPath(cur, next))
- GetShortPath(next, pPath);
- // 右
- next = cur;
- next._col+= 1;
- if(IsAccessInShortPath(cur, next))
- GetShortPath(next, pPath);
- // 四个方向都走不通 开始回朔, pop 掉 path 栈里保存的路径坐标
- StackPop(pPath);
- }
递归的过程可参考下图:
最后再简单测一下:
- void TestMaze()
- {
- Pos entry;
- entry._col = 1;
- entry._row = 6;
- /*GetPath(entry);
- PrintMaze(maze);*/
- Stack path;
- StackInit(&path);
- StackInit(&shortPath);
- GetShortPath(entry, &path);
- PrintMaze(maze);
- while(StackEmpty(&shortPath) != 0)
- {
- Pos cur = StackTop(&shortPath);
- printf("(%d,%d)<-", cur._row, cur._col);
- StackPop(&shortPath);
- }
- printf("入口 \ n");
- }
结果:
小结一下:
1. 刷新 shortPath 里保存的路径, 需要将 path 栈里存的路径整体拷贝过来, 若将实现 path 栈底层的_array 直接赋值给 shortPath._array
以本迷宫为例, 它会先找到 厂 型的路线, 于是 shortPath._array 被赋值为 path->_array 保存了路径, 而找第二条路径时在递归到 < 4, 5 > 处会停止, 算法结束, 于是导致
shortPath._array 存放的路径不完整; 而整体拷贝的话, 由于没到规定出口出, shortPath._array 并未刷新, 还保存的是上一条路径 保证正确性
2. 实现该迷宫时, 默认设置出口为 col = 6 的位置, 其实应该将出口的信息作为参数传入找路径的函数中, 大家可以自行再优化
来源: https://www.cnblogs.com/tp-16b/p/8511270.html