大家好，又见面了，我是你们的朋友全栈君。
本总结是是个人为防止遗忘而作，不得转载和商用。
题目
一只老鼠位于迷宫左上角(0,0)，迷宫中的数字9处有块大奶酪。0表示墙，1表示可通过路径。试给出一条可行的吃到奶酪的路径；若没有返回空。
假定迷宫是4连通的，即：老鼠只能上下左右走，不能斜着走。
算法描述
这实际上就是练习深度优先搜索。
PS：个人感觉深度优先搜索就是个有点门道的暴力求解….
解法：假定当前位于(i,j)处，则依次计算(i-1,j),(i+1,j),(i,j-1), (i,j+1)4个相邻位置，如果相邻位置不是墙，则可以通过。然后递归该过程。
代码
void MousePath(const vector<vector<int>>& chess)
{
// 棋盘都是坐标，于是用int表示
vector<pair<int, int>> path;
// 初始化棋盘，所有值都标为False，即每个左边都还未被访问过
vector<vector<bool>> visit(chess.size(),vector<bool>(chess[0].size(), false));
// 开始路径搜索
path.push_back(make_pair(0, 0)); // 从0,0开始
visit[0][0] = true; // 0,0被访问过
Search( chess, 0, 0, path, visit ); // 开始搜索，对于棋盘chess，从0,0开始，记录路径path，访问的节点放置在visit。
}
bool Search(const vector< vector<int>>& chess, int i, int j, vector<pair<int, int>>&path, vector<vector<bool>>&visit)
{
// 如果为9，那就找到了，打印path，返回ture
if(chess[i][j] == 9) {
Print(path);
return true;
}
// 相对于当前的(i,j)点，(i-1, j)，(i+1, j)，(i, j-1)，(i, j+1) 就是(-1, 0)，(1, 0)，(0, -1)，(0, 1)，于是iNext就是这四个点的i值，jNext就是相应的j值。
int iNext[] = {0, 0, -1, 1};
int jNext[] = {-1, 1, 0, 0};
int iCur, jCur;
// 棋盘大小是m*n的
int m = (int)chess.size();
int n = (int)chess[0].size();
// 4代表4连通。
for(int k = 0, k < 4; k++) {
// 当前的(i,j)偏移一位。
iCur = i+iNext[k];
jCur = j+jNext[k];
// 如果越界，则不可行
if((iCur < 0) || (iCur >= m ) || (jCur < 0) || (jCur >= n ) continue;
// 要求iCur和jCur从来没到达过且不是墙
if(!visit[iCur][jCur] && (chess[iCur][jCur] != 0)) {
// 把iCur和jCur放置在路径中
path.push_back(make_pair(iCur, jCur));
// 把iCur和jCur设置为已访问
visit[iCur][jCur] = true;
// 继续搜索
if(Search(chess, iCur, jCur, path, visit)) {
// 如果求所有路径，则将下句替换成all.push_back(path);
return true;
}
// 从(iCur,jCur)找不到可行路径，把iCur和jCur pop出去，然后回溯一下继续探测。
path.pop_back();
visit[iCur][jCur] = false;
}
}
return false;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/125382.html原文链接：https://javaforall.net
