小杰作--找迷宫出口路线
呼啦啦~忙了两天
终于完成迷宫第一代了
无聊发个来看看~顺便求大神指点
对哦，这个没有实现找最短路线功能，只能判断有没有出口和找出口路线~
发过来看看，感觉怎么样都能看懂或多或少的~
程序代码：#include<stdio.h>
#include<stdlib.h>
#define N 10
typedef struct Node
{
int ww;//四个方向
int ss;
int aa;
int dd;
int count;//计算重复走过路线的次数~
char map;//地图
}Node;
Node S[N][N];//迷宫数组
typedef struct SS
{
int x;
int y;
}SS;
SS Self;//自己的当前位置
void print()//打印地图
{
int i,j;
for (i=0;i<N;i++,printf("\n"))
for (j=0;j<N;j++)
printf("%c",S[i][j].map);
}
void begin(char k[][N])//初始化数据~
{
int i=0;
int j=0;
for (i=0;i<N;i++)
for (j=0;j<N;j++)
{
S[i][j].map=k[i][j];
if (k[i][j]=='S')//找到初始位置
{
Self.x=i;
Self.y=j;
}
}
print();//打印初始化地图
}
int JUDGE_RUN(int count,int i,int j,int toward)//判断移动位置
{
switch (count)
{
case 1:return(S[i-1][j].map!='*'&&i-1>=0&&toward!=1&&S[i][j].ww)?1:0;
case 2:return(S[i+1][j].map!='*'&&i+1<=N&&toward!=2&&S[i][j].ss)?1:0;
case 3:return(S[i][j-1].map!='*'&&j-1>=0&&toward!=3&&S[i][j].aa)?1:0;
case 4:return(S[i][j+1].map!='*'&&j+1<=N&&toward!=4&&S[i][j].dd)?1:0;
default:break;
}
return 0;
}
void JUDGE_MAP()
{
int i=0;
int j=0;
for (i=0;i<N;i++)
for (j=0;j<N;j++)
{
S[i][j].ww=JUDGE_RUN(1,i,j,0)?0:1;//判断是否可以移动,此时toward是无指向的(即为0)~
S[i][j].ss=JUDGE_RUN(2,i,j,0)?0:1;
S[i][j].aa=JUDGE_RUN(3,i,j,0)?0:1;
S[i][j].dd=JUDGE_RUN(4,i,j,0)?0:1;
S[i][j].count=0;//设置重复走过的路线次数为0~
}
printf("\n");
}
void JUDGE_WIN()
{
if (S[Self.x][Self.y].map=='E')
{
printf("Yes\n");
print();
exit(0);//直接退出处理~
}
}
void change(int toward)//toward指的是当前方向~1 2 3 4分别代表上下左右~
{
int i=Self.x; //获取当前位置
int j=Self.y;
JUDGE_WIN();//判断是否找到出口~
++S[i][j].count;//重复走过路线的次数要加1
if (S[i][j].map!='S')//保留初始化位置(其实可以不用)
S[i][j].map='o';//标记走过路线
if (JUDGE_RUN(1,i,j,toward))
{
--Self.x; //移动当前位置
S[i][j].ww=0; //清除当前位置方向
change(2); //避免回头走，方向处理~
++Self.x; //退栈要改变当前位置
}
if (JUDGE_RUN(2,i,j,toward))
{
++Self.x;
S[i][j].ss=0;
change(1);
--Self.x;
}
if (JUDGE_RUN(3,i,j,toward))
{
--Self.y;
S[i][j].aa=0;
change(4);
++Self.y;
}
if (JUDGE_RUN(4,i,j,toward))
{
++Self.y;
S[i][j].dd=0;
change(3);
--Self.y;
}
--S[i][j].count; //退栈要减少重复走过次数
if (S[i][j].count==0&&S[i][j].map!='S')
S[i][j].map=' '; //清除走过路线
return;
}
int main()//'S'为起点，'E'为终点
{
char k[N][N]= //地图大小改了迷宫会错位，很麻烦的~改大小要注意一下~
{
{"**********"},
{"* S* *E*"},
{"* *** ** *"},
{"* * * * *"},
{"* *"},
{"*** * ** *"},
{"** * * *"},
{"** ** ** *"},
{"* * * *"},
{"**********"},
};
begin(k);
JUDGE_MAP();
change(0);
printf("NO!\n"); //找不到出口~
return 0;
}[此贴子已经被作者于2016-12-19 13:53编辑过]
参考了大神的代码，感觉以前高不可攀的迷宫算法现在做最基础的几乎是水到渠成了，这个算法很值得借鉴，学习了
还是要多多向大神学习一下才行~
