用栈求解迷宫问题的所有路径及最短路径程序（纯c语言） |
您所在的位置：网站首页 › 关于自信的名人素材事例200字 › 用栈求解迷宫问题的所有路径及最短路径程序（纯c语言） |
用栈求解迷宫问题的所有路径及最短路径程序（纯c语言）
|
参考了这个博客 学校作业，在各种地方搜了半天，看别人的要么就是有点错，要么就是很复杂用了不少我不知道的库，还要么就是只求了一条路径，还要么就是用了c++没学过。 写了半天，写出了一个应该是比较简单的方法，应该是还能优化，不过作业能跑就行，懒得搞了。有更好的想法，欢迎交流。 ---------------------------------------------------------------------------------------- 正文 讲讲思路吧，首先定义一下迷宫的方块 typedef struct { int i;//行 int j;//列 int di;//探索方向 }box;再定义一下栈 typedef struct { box data[maxsize]; int top; }stack;//定义栈的类型这里面主要的就是di探索方向 实现试探的代码如下采用了switch的方法 switch (di)//试探方块 { case 0:a = i - 1, b = j; break; case 1:a = i, b = j + 1; break; case 2:a = i + 1, b = j; break; case 3:a = i, b = j - 1; break; }如试探的方块是可以通过的那就入栈，要是所有方向都不行就退栈，回到上一个方块，以此类推，直到试探到方块是出口。同时为了防止重复经过方块，再入栈时把迷宫数组在这一点变成-1（0是路，1是墙） 比较关键的是怎么探查出所有的路径。 我的想法是在第一次找到出口时，在输出路径后，就直接退栈，再利用continue结束这次循环。达到回溯道路的作用。 退栈后回到上一个方块 ，换一个方向再继续试探，重复以上的过程即可。 再就是算最短路径，直接再找到出口的时候比较一下top指针就好了 if (s->top +1< min)//比较路径长度 { min = s->top+1;//长度 _min = count;//最短长度对应的第几条路 }完整代码如下 #include #define maxsize 100 int mg[6][6]={ {1,1,1,1,1,1},{1,0,0,0,1,1}, {1,0,1,0,0,1},{1,0,0,0,1,1}, {1,1,0,0,0,1},{1,1,1,1,1,1} }; //设置迷宫 1为墙，0为路 typedef struct { int i, j, di; }box;//定义栈的元素 typedef struct { box data[maxsize]; int top; }stack;//定义栈的类型 void Initstack(stack*& s)//初始化栈 { s = new stack; s->top = -1; } bool push(stack*& s, box e)//压栈 { if (s->top == maxsize - 1) return false; s->top++; s->data[s->top] = e; return true; } bool pop(stack*& s, box &e)//出栈 { if (s->top == -1) return false; e = s->data[s->top]; s->top--; return true; } bool gettop(stack*& s, box& e) //取栈顶元素 { if (s->top == -1) return false; e = s->data[s->top]; return true; } bool mgpath(int x, int y, int xi, int yi)//寻找路径 起点坐标(x,y)终点坐标(xi,yi) { int min = 100, _min=1; int i, j, di,count=1,k,a,b; int flag = 0;//有解的标志 box e; bool find; stack* s; Initstack(s);//初始化栈 e.i = x;//设置入口 e.j = y; e.di = -1; push(s, e); mg[x][y] = -1;//入口设为-1防止重复走 while (s->top != -1)//不为空栈时循环 { gettop(s, e);//取栈顶方块e(i,j) i = e.i; j = e.j; di = e.di; if (i == xi && j == yi)//找到出口输出该路径 { flag = 1; if (s->top +1< min)//比较路径长度 { min = s->top+1;//长度 _min = count;//最短长度对应的第几条路 } printf("第%d条路径如下：\n", count++); for (k = 0; k top; k++) printf("(%d,%d)\t", s->data[k].i, s->data[k].j); printf("\n"); pop(s, e);//回溯道路 mg[e.i][e.j] = 0; continue;//结束当次循环 } find = false; while (di < 4 && !find)//找下一个可走方块 { di++;//初值为-1 switch (di)//试探方块 { case 0:a = i - 1, b = j; break; case 1:a = i, b = j + 1; break; case 2:a = i + 1, b = j; break; case 3:a = i, b = j - 1; break; } if (mg[a][b] == 0) find = true;//找到可走方块(a,b) } if (find)//找到 { s->data[s->top].di = di; e.i = a; e.j = b; e.di = -1; push(s, e);//方块（a，b）入栈 mg[a][b] = -1;//设为-1防止重复走 } else //找不到 { pop(s, e); mg[e.i][e.j] = 0;//恢复退栈方块 } } if (flag == 1) { printf("最短路径为路径%d\n", _min); printf("最短路径长度为%d\n", min); return true; } delete(s);//释放栈 return false; } int main() { if (!mgpath(1, 1, 4, 4)) printf("该迷宫问题没有解！\n"); return 0; }结果示例
|
【本文地址】
今日新闻 |
推荐新闻 |