c语言实现迷宫最优路径选择.doc

中国计量学院实验报告实验课程：算法与数据结构实验名称：迷宫的最优路径班 级：学 号：姓 名：实验日期：2013-5-20一 实验题目：输入一迷宫查找并输出迷宫的最优路径实验成绩： 指导教师：二 算法说明1.定义一个结构体来表示起点和末点的坐标,定义一个数组来存放迷宫.struct elem int x;/行 int y;/列; /定义结构体int M1010;2.给数组中空白处赋上从起点到该处步骤的值. int find(int n)for(i=0;i9;i+)for(j=0;j10;j+)if(Mij=n)if (Mij+1=0) Mij+1=n+1;else if(Mij+1n+1) Mij+1=n+1;if (Mi+1j=0) Mi+1j=n+1;else if(Mi+1jn+1) Mi+1j=n+1;if (Mij-1=0) Mij-1=n+1;else if(Mij-1n+1) Mij-1=n+1;if (Mi-1j=0) Mi-1j=n+1;else if(Mi-1jn+1) Mi-1j=n+1;3.给最优路径附上特定的值,方便最后的输出.for (;)if(Mq.x+1q.y=(n-1) q.x+;Mq.xq.y=0;else if(Mq.xq.y-1=(n-1) q.y-;Mq.xq.y=0; else if(Mq.x-1q.y=(n-1) q.x-;Mq.xq.y=0; else if(Mq.xq.y+1=(n-1) q.y+;Mq.xq.y=0;n-;if(e.x=q.xe.y=q.y) Me.xe.y=0; break;三 测试结果四 分析与探讨程序结果正确，但是没有涉及到栈内容，使用栈可以对程序进一步改进。五 附录：源代码中国计量学院实验报告#include stdio.h#include stdlib.hstruct elem int x;/行 int y;/列 int di;/方向，di=1代表右,di=2代表下,di=3代表左,di=4代表上; /定义结构体struct elem e, q;int M1010=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, 0, 0,-1, 0, 0, 0,-1, 0,-1, -1, 0, 0,-1, 0, 0, 0,-1, 0,-1, -1, 0, 0, 0, 0,-1,-1, 0, 0,-1, -1, 0,-1,-1,-1, 0, 0, 0, 0,-1, -1, 0, 0, 0,-1, 0, 0, 0, 0,-1, -1, 0,-1, 0, 0, 0,-1, 0, 0,-1, -1, 0,-1,-1,-1, 0,-1,-1, 0,-1, -1,-1, 0, 0, 0, 0, 0, 0, 0,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1;int n=1,i,j;/从起点到某个位置的步骤int find(int n)for(i=0;i9;i+)for(j=0;j10;j+)if(Mij=n)if (Mij+1=0) Mij+1=n+1;else if(Mij+1n+1) Mij+1=n+1;if (Mi+1j=0) Mi+1j=n+1;else if(Mi+1jn+1) Mi+1j=n+1;if (Mij-1=0) Mij-1=n+1;else if(Mij-1n+1) Mij-1=n+1;if (Mi-1j=0) Mi-1j=n+1;else if(Mi-1jn+1) Mi-1j=n+1;int main(void)int k;/*printf(请输入迷宫:n);for(i=0;i10;i+)for (j=0;j10;j+)scanf(%d,Mij);*/ printf(迷宫为:n);for (i=0;i10;i+) /显示迷宫for (j=0;j10;j+)if(Mij=-1) printf( #);else printf( );if(j=9) printf(n);printf(请输入入口的横纵坐标:n); scanf(%d %d,e.x,e.y);if(Me.xe.y=-1)printf(迷宫走不通n);Me.xe.y=n; printf(请输入出口的横纵坐标:n); scanf(%d %d,q.x,q.y);if(Mq.xq.y=-1)printf(迷宫走不通n) ;for(k=0;k20;k+)find(n);n+;n=Mq.xq.y;Mq.xq.y=0;for (;)if(Mq.x+1q.y=(n-1) q.x+;Mq.xq.y=0;else if(Mq.xq.y-1=(n-1) q.y-;Mq.xq.y=0; else if(Mq.x-1q.y=(n-1) q.x-;Mq.xq.y=0; else if(Mq.xq.y+1=(n-1) q.y+;Mq.xq.y=0;n-;if(e.x=q.xe.y=q.y) Me.xe.y=0; break; printf(最优路径为:n);for (i=0;i10;i+) /显示迷宫和路径，其中#代表墙，0代表路径，空白处代表