如何用C语言实现求迷宫的最短路径？
#includestdio.h
#includestdlib.h
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定义迷宫，0表示能走的块，1表示不能走，在外围加上一圈不能走的块
{
{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}
};
struct
{
int i,j; //块的位置
int pre; //本路径中上一块在队列中的下标
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front=rear!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xej==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di4;di++)
{
switch(di) //四个方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循环
}
}
}
return 0;
}
void print(int n) //输出 路径算法
{
int k=n,j,m=1;
printf(“\n”);
do //将输出的路径上的所有pre改为-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf(“迷宫最短路径如下：\n”);
k=0;
while(kMax)
{
if(Qu[k].pre==-1)
{
printf(“\t(%d,%d)”,Qu[k].i,Qu[k].j);
if(m%5==0)
printf(“\n”);
m++;
}
k++;
}
printf(“\n”);
}
int main()
{
mgpath(1,1,M,N);
system(“pause”);
return 0;
}
c语言做的迷宫问题
#include stdio.h
#include stdlib.h
#include malloc.hstruct node
{
int sign;//标识,0什么都不在,1在open中,2在closed中
int flag;//标志位 0/1,0可以走,1不可以走
int f,g,h;//判断函数
int x,y;//坐标
int old;//是否old节点,0非,1是
};struct link
{
node fnode;
link *next;
link *pri;
};link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;int maze_flag[7][7]={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宫的数组,0可以走,1不可以走node maze[7][7];int judge(node n)//判断函数,判断n节点是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}void in_open(node n)//将n节点放入open表
{
p=open;
while(p-next!=open)
{
if(n.f=p-fnode.f)
{
p-next-pri=(link *)malloc(sizeof(link));
p-next-pri-pri=p;
p=p-next;
p-pri-next=p;
p-pri-pri-next=p-pri;
p=p-pri;
p-fnode.flag=n.flag;
p-fnode.f=n.f;
p-fnode.g=n.g;
p-fnode.h=n.h;
p-fnode.x=n.x;
p-fnode.y=n.y;
p-fnode.old=n.old;
p-fnode.sign=n.sign=1;
}
else
p=p-next;
}
open-pri=(link *)malloc(sizeof(link));
open-pri-pri=p;
open-pri-next=open;
p-next=open-pri;
p=p-next;
p-fnode.flag=n.flag;
p-fnode.f=n.f;
p-fnode.g=n.g;
p-fnode.h=n.h;
p-fnode.x=n.x;
p-fnode.y=n.y;
p-fnode.old=n.old;
p-fnode.sign=n.sign=1;
}void out_open(node n)//将n节点从open表中移出
{
p=open;
while(p-next!=open)
{
if(n.f=p-fnode.f)
{
link *p1;
p1=p-next;
p-next=p-next-next;
p-next-pri=p;
free(p1);
n.sign=0;
}
else
p=p-next;
}
}void in_closed(node n)//将n节点放入closed表
{
while(q-next!=closed)
{
if(n.f=q-fnode.f)
{
q-next-pri=(link *)malloc(sizeof(link));
q-next-pri-pri=q;
q=q-next;
q-pri-next=p;
q-pri-pri-next=q-pri;
q=q-pri;
q-fnode.flag=n.flag;
q-fnode.f=n.f;
q-fnode.g=n.g;
q-fnode.h=n.h;
q-fnode.x=n.x;
q-fnode.y=n.y;
q-fnode.old=n.old;
q-fnode.sign=n.sign=2;
}
else
q=q-next;
}
closed-pri=(link *)malloc(sizeof(link));
closed-pri-pri=q;
closed-pri-next=closed;
q-next=closed-pri;
q=q-next;
q-fnode.flag=n.flag;
q-fnode.f=n.f;
q-fnode.g=n.g;
q-fnode.h=n.h;
q-fnode.x=n.x;
q-fnode.y=n.y;
q-fnode.old=n.old;
q-fnode.sign=n.sign=2;
}void out_closed(node n)//将n节点从closed表中移出
{
q=closed;
while(q-next!=closed)
{
if(n.f=q-fnode.f)
{
link *q1;
q1=q-next;
q-next=q-next-next;
q-next-pri=q;
free(q1);
n.sign=0;
}
else
q=q-next;
}
}void in_bestnode(node n)//将n节点设为bestnode节点
{
while(r-next!=bestnode)
{
if(n.f=r-fnode.f)
{
r-next-pri=(link *)malloc(sizeof(link));
r-next-pri-pri=r;
r=r-next;
r-pri-next=r;
r-pri-pri-next=r-pri;
r=r-pri;
r-fnode.flag=n.flag;
r-fnode.f=n.f;
r-fnode.g=n.g;
r-fnode.h=n.h;
r-fnode.x=n.x;
r-fnode.y=n.y;
r-fnode.old=n.old;
}
else
r=r-next;
}
bestnode-pri=(link *)malloc(sizeof(link));
bestnode-pri-pri=r;
bestnode-pri-next=bestnode;
r-next=bestnode-pri;
r=r-next;
r-fnode.flag=n.flag;
r-fnode.f=n.f;
r-fnode.g=n.g;
r-fnode.h=n.h;
r-fnode.x=n.x;
r-fnode.y=n.y;
r-fnode.old=n.old;
}void out_bestnode(node n)//将n节点的bestnode去掉
{
r=bestnode;
while(r-next!=bestnode)
{
if(n.f=p-fnode.f)
{
link *r1;
r1=r-next;
r-next=r-next-next;
r-next-pri=r;
free(r1);
}
else
r=r-next;
}
}void in_successor(node n)//将n节点设置为successor节点
{
s=successor;
while(s-next!=successor)
{
if(n.f=s-fnode.f)
{
s-next-pri=(link *)malloc(sizeof(link));
s-next-pri-pri=s;
s=p-next;
s-pri-next=s;
s-pri-pri-next=s-pri;
s=s-pri;
s-fnode.flag=n.flag;
s-fnode.f=n.f;
s-fnode.g=n.g;
s-fnode.h=n.h;
s-fnode.x=n.x;
s-fnode.y=n.y;
s-fnode.old=n.old;
}
else
s=s-next;
}
successor-pri=(link *)malloc(sizeof(link));
successor-pri-pri=s;
successor-pri-next=successor;
s-next=successor-pri;
s=s-next;
s-fnode.flag=n.flag;
s-fnode.f=n.f;
s-fnode.g=n.g;
s-fnode.h=n.h;
s-fnode.x=n.x;
s-fnode.y=n.y;
s-fnode.old=n.old;
}void out_successor(node n)//将n节点的successor去掉
{
s=successor;
while(s-next!=successor)
{
if(n.f=p-fnode.f)
{
link *s1;
s1=s-next;
s-next=s-next-next;
s-next-pri=s;
free(s1);
}
else
s=s-next;
}
}void print(link *n)//输出link类型的表n
{
link *forprint;
forprint=n;
printf(“the key is “);
while(forprint-next!=n)
printf(“(%d,%d)\n”,forprint-fnode.x,forprint-fnode.y);
}int main()
{
//初始化部分
//这部分的功能是将二维的整形数组赋值给node型的二维数组
int i=0,j=0;
for(i=0;i7;i++)
for(j=0;j7;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
if(maze[i][j].flag==0)
{
maze[i][j].h=6-i+6-j;
maze[i][j].sign=maze[i][j].f=maze[i][j].g=maze[i][j].old=0;
}
else
maze[i][j].h=-1;
}
for(i=0;i7;i++)//输出迷宫示意图
{
for(j=0;j7;j++)
{
printf(“%2d”,maze_flag[i][j]);
}
printf(“\n”);
}
//这部分的功能是将open,closed,bestnode表初始化,都置为空表
p=open=(link *)malloc(sizeof(link));
open-next=open;
open-pri=open;
q=closed=(link *)malloc(sizeof(link));
closed-next=closed;
closed-pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode-next=bestnode;
bestnode-pri=bestnode;
//将第一个元素即(0,0)节点放入open表,开始算法
in_open(maze[0][0]);
maze[0][0].f=maze[0][0].h;
link *s2;
s2=successor;
if(open-next!=open)//open表为空时则失败退出
{
while(1)
{
in_bestnode(open-fnode);//将open表的第一个元素放入bestnode中
in_closed(maze[open-fnode.x][open-fnode.y]);//将open表的第一个元素放入closed中
maze[open-fnode.x][open-fnode.y].g++;//将open表的第一个元素的g值加一,表示已经走了一步
out_open(maze[open-fnode.x][open-fnode.y]);//将open表的第一个元素删除 if(bestnode-fnode.x==6bestnode-fnode.y==6)//若bestnode是目标节点,则成功退出
{
printf(“succes!!\nthen print the key:\n”);
print(closed);
break;
}
else//若bestnode不是目标节点,则扩展其临近可以走的节点为successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0j==0)//若为(0,0),则判断右边和下边的元素
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==0j==6)//若为(0,6),则判断左边和下边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6j==0)//若为(6,0),则判断左边和上边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==6j==6)//若为(6,6),则判断左边和上边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==0)//若为第一行的元素(不在角上),则判断左边,下边和右边
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6)//若为第七行的元素(不在角上),则判断左边,上边和右边
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
}
else if(j==0)//若为第一列的元素(不在角上),则判断右边,下边和上边
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
}
else if(j==6)//若为第七列的元素(不在角上),则判断左边,上边和上边
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
}
else//若为中将的元素,则判断四个方向的节点
{
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
}
while(s2-next!=successor)//对所有的successor节点进行下列操作
{
maze[s2-fnode.x][s2-fnode.y].g=bestnode-fnode.g+bestnode-fnode.h;//计算g(suc)=g(bes)+h(bes,suc)
if(s2-fnode.sign==1)//若在open表中,则置为old,记下较小的g,并从open表中移出,放入closed表中
{
s2-fnode.old=1;
if(s2-fnode.gmaze[s2-fnode.x][s2-fnode.y].g)
{
maze[s2-fnode.x][s2-fnode.y].g=s2-fnode.g;
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
out_open(maze[s2-fnode.x][s2-fnode.y]);
in_closed(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].old=0;
}
else
continue;
}
else if(s2-fnode.sign==2)//若在closed表中,则置为old,记下较小的g,并将old从closed表中移出,将较小的g的节点放入closed表中
{
s2-fnode.old=1;
if(s2-fnode.gmaze[s2-fnode.x][s2-fnode.y].g)
{
maze[s2-fnode.x][s2-fnode.y].g=s2-fnode.g;
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
out_closed(maze[s2-fnode.x][s2-fnode.y]);
in_closed(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,则将此节点放入open表中,并计算此节点的f值
{
in_open(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
}
s2=s2-next;
}
s2=successor;
}
}
else
printf(“error!!This maze does not have the answer!”);
return(0);
}
C语言编程 迷宫问题(队列)
c#界面绘制的时候，底层重绘每次会清除画布背景，然后再全部重新绘制，这才是导致闪烁最主要的原因。于是重载消息发送函数操作，禁掉这条消息。代码如下：
protected override void WndProc(ref Message m)
{
if (m.Msg == 0x0014) // 禁掉清除背景消息
return;
base.WndProc(ref m);
}
C语言：迷宫，求程序，快哭了！好虐。。。
输入这段就不用写了吧。比较简单
A 输入迷宫
用2维数组把这个 迷宫存下来就行了。 墙用0表示 路用1表示。 或者直接用字符的2维数组也行。设为公共变量 migong[m][m] 用公共变量存 m
B 走通判定 (这里以一个迷宫为例，多个迷宫的话 输入那边处理一下就好了，反正中心思想就是1个迷宫用一个2维数组存)
是否能走通的判定。 用迭代法
1 判定周围是否有e(因为e在右下角 只用判断下方和右方就可以了)
2 没有向右走
3 右是墙的话向下走
4 下是墙的话向左走
5 左是墙的话向上走。
bool findway(int startx,int,starty)
{
int end = m – 1;
if(x + 1 == end y == end || x == end y + 1 == end )
{
return true; //可以走通 返回YES
}
else if (x + 1 end migong[x + 1][y] != ‘#’) //当前点不处于最右侧 且右侧点不为墙的时候
{
findway(startx + 1,starty); //右移
}
else if(y + 1 end migong[x][y+1] !=’#’ ) //当前点不处于最下侧 且下侧点不为墙的时候
{
findway(startx,starty + 1); //下移
}
……………………….//按照这个思路做 以下省略
}
然后主函数中调用 findway(0,0) 就OK了。
写得比较简单，不好意思。
急求：C语言实现的迷宫问题代码！
#include stdio.h
#include stdlib.h
#include malloc.h
struct node
{
int sign;//标识,0什么都不在,1在open中,2在closed中
int flag;//标志位 0/1,0可以走,1不可以走
int f,g,h;//判断函数
int x,y;//坐标
int old;//是否old节点,0非,1是
};
struct link
{
node fnode;
link *next;
link *pri;
};
link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;
int maze_flag[7][7]={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宫的数组,0可以走,1不可以走
node maze[7][7];
int judge(node n)//判断函数,判断n节点是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}
void in_open(node n)//将n节点放入open表
{
p=open;
while(p-next!=open)
{
if(n.f=p-fnode.f)
{
p-next-pri=(link *)malloc(sizeof(link));
p-next-pri-pri=p;
p=p-next;
p-pri-next=p;
p-pri-pri-next=p-pri;
p=p-pri;
p-fnode.flag=n.flag;
p-fnode.f=n.f;
p-fnode.g=n.g;
p-fnode.h=n.h;
p-fnode.x=n.x;
p-fnode.y=n.y;
p-fnode.old=n.old;
p-fnode.sign=n.sign=1;
}
else
p=p-next;
}
open-pri=(link *)malloc(sizeof(link));
open-pri-pri=p;
open-pri-next=open;
p-next=open-pri;
p=p-next;
p-fnode.flag=n.flag;
p-fnode.f=n.f;
p-fnode.g=n.g;
p-fnode.h=n.h;
p-fnode.x=n.x;
p-fnode.y=n.y;
p-fnode.old=n.old;
p-fnode.sign=n.sign=1;
}
void out_open(node n)//将n节点从open表中移出
{
p=open;
while(p-next!=open)
{
if(n.f=p-fnode.f)
{
link *p1;
p1=p-next;
p-next=p-next-next;
p-next-pri=p;
free(p1);
n.sign=0;
}
else
p=p-next;
}
}
void in_closed(node n)//将n节点放入closed表
{
while(q-next!=closed)
{
if(n.f=q-fnode.f)
{
q-next-pri=(link *)malloc(sizeof(link));
q-next-pri-pri=q;
q=q-next;
q-pri-next=p;
q-pri-pri-next=q-pri;
q=q-pri;
q-fnode.flag=n.flag;
q-fnode.f=n.f;
q-fnode.g=n.g;
q-fnode.h=n.h;
q-fnode.x=n.x;
q-fnode.y=n.y;
q-fnode.old=n.old;
q-fnode.sign=n.sign=2;
}
else
q=q-next;
}
closed-pri=(link *)malloc(sizeof(link));
closed-pri-pri=q;
closed-pri-next=closed;
q-next=closed-pri;
q=q-next;
q-fnode.flag=n.flag;
q-fnode.f=n.f;
q-fnode.g=n.g;
q-fnode.h=n.h;
q-fnode.x=n.x;
q-fnode.y=n.y;
q-fnode.old=n.old;
q-fnode.sign=n.sign=2;
}
void out_closed(node n)//将n节点从closed表中移出
{
q=closed;
while(q-next!=closed)
{
if(n.f=q-fnode.f)
{
link *q1;
q1=q-next;
q-next=q-next-next;
q-next-pri=q;
free(q1);
n.sign=0;
}
else
q=q-next;
}
}
void in_bestnode(node n)//将n节点设为bestnode节点
{
while(r-next!=bestnode)
{
if(n.f=r-fnode.f)
{
r-next-pri=(link *)malloc(sizeof(link));
r-next-pri-pri=r;
r=r-next;
r-pri-next=r;
r-pri-pri-next=r-pri;
r=r-pri;
r-fnode.flag=n.flag;
r-fnode.f=n.f;
r-fnode.g=n.g;
r-fnode.h=n.h;
r-fnode.x=n.x;
r-fnode.y=n.y;
r-fnode.old=n.old;
}
else
r=r-next;
}
bestnode-pri=(link *)malloc(sizeof(link));
bestnode-pri-pri=r;
bestnode-pri-next=bestnode;
r-next=bestnode-pri;
r=r-next;
r-fnode.flag=n.flag;
r-fnode.f=n.f;
r-fnode.g=n.g;
r-fnode.h=n.h;
r-fnode.x=n.x;
r-fnode.y=n.y;
r-fnode.old=n.old;
}
void out_bestnode(node n)//将n节点的bestnode去掉
{
r=bestnode;
while(r-next!=bestnode)
{
if(n.f=p-fnode.f)
{
link *r1;
r1=r-next;
r-next=r-next-next;
r-next-pri=r;
free(r1);
}
else
r=r-next;
}
}
void in_successor(node n)//将n节点设置为successor节点
{
s=successor;
while(s-next!=successor)
{
if(n.f=s-fnode.f)
{
s-next-pri=(link *)malloc(sizeof(link));
s-next-pri-pri=s;
s=p-next;
s-pri-next=s;
s-pri-pri-next=s-pri;
s=s-pri;
s-fnode.flag=n.flag;
s-fnode.f=n.f;
s-fnode.g=n.g;
s-fnode.h=n.h;
s-fnode.x=n.x;
s-fnode.y=n.y;
s-fnode.old=n.old;
}
else
s=s-next;
}
successor-pri=(link *)malloc(sizeof(link));
successor-pri-pri=s;
successor-pri-next=successor;
s-next=successor-pri;
s=s-next;
s-fnode.flag=n.flag;
s-fnode.f=n.f;
s-fnode.g=n.g;
s-fnode.h=n.h;
s-fnode.x=n.x;
s-fnode.y=n.y;
s-fnode.old=n.old;
}
void out_successor(node n)//将n节点的successor去掉
{
s=successor;
while(s-next!=successor)
{
if(n.f=p-fnode.f)
{
link *s1;
s1=s-next;
s-next=s-next-next;
s-next-pri=s;
free(s1);
}
else
s=s-next;
}
}
void print(link *n)//输出link类型的表n
{
link *forprint;
forprint=n;
printf(“the key is “);
while(forprint-next!=n)
printf(“(%d,%d)\n”,forprint-fnode.x,forprint-fnode.y);
}
int main()
{
//初始化部分
//这部分的功能是将二维的整形数组赋值给node型的二维数组
int i=0,j=0;
for(i=0;i7;i++)
for(j=0;j7;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
if(maze[i][j].flag==0)
{
maze[i][j].h=6-i+6-j;
maze[i][j].sign=maze[i][j].f=maze[i][j].g=maze[i][j].old=0;
}
else
maze[i][j].h=-1;
}
for(i=0;i7;i++)//输出迷宫示意图
{
for(j=0;j7;j++)
{
printf(“%2d”,maze_flag[i][j]);
}
printf(“\n”);
}
//这部分的功能是将open,closed,bestnode表初始化,都置为空表
p=open=(link *)malloc(sizeof(link));
open-next=open;
open-pri=open;
q=closed=(link *)malloc(sizeof(link));
closed-next=closed;
closed-pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode-next=bestnode;
bestnode-pri=bestnode;
//将第一个元素即(0,0)节点放入open表,开始算法
in_open(maze[0][0]);
maze[0][0].f=maze[0][0].h;
link *s2;
s2=successor;
if(open-next!=open)//open表为空时则失败退出
{
while(1)
{
in_bestnode(open-fnode);//将open表的第一个元素放入bestnode中
in_closed(maze[open-fnode.x][open-fnode.y]);//将open表的第一个元素放入closed中
maze[open-fnode.x][open-fnode.y].g++;//将open表的第一个元素的g值加一,表示已经走了一步
out_open(maze[open-fnode.x][open-fnode.y]);//将open表的第一个元素删除
if(bestnode-fnode.x==6bestnode-fnode.y==6)//若bestnode是目标节点,则成功退出
{
printf(“succes!!\nthen print the key:\n”);
print(closed);
break;
}
else//若bestnode不是目标节点,则扩展其临近可以走的节点为successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0j==0)//若为(0,0),则判断右边和下边的元素
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==0j==6)//若为(0,6),则判断左边和下边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6j==0)//若为(6,0),则判断左边和上边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==6j==6)//若为(6,6),则判断左边和上边的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==0)//若为第一行的元素(不在角上),则判断左边,下边和右边
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6)//若为第七行的元素(不在角上),则判断左边,上边和右边
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
}
else if(j==0)//若为第一列的元素(不在角上),则判断右边,下边和上边
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
}
else if(j==6)//若为第七列的元素(不在角上),则判断左边,上边和上边
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
}
else//若为中将的元素,则判断四个方向的节点
{
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
}
while(s2-next!=successor)//对所有的successor节点进行下列操作
{
maze[s2-fnode.x][s2-fnode.y].g=bestnode-fnode.g+bestnode-fnode.h;//计算g(suc)=g(bes)+h(bes,suc)
if(s2-fnode.sign==1)//若在open表中,则置为old,记下较小的g,并从open表中移出,放入closed表中
{
s2-fnode.old=1;
if(s2-fnode.gmaze[s2-fnode.x][s2-fnode.y].g)
{
maze[s2-fnode.x][s2-fnode.y].g=s2-fnode.g;
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
out_open(maze[s2-fnode.x][s2-fnode.y]);
in_closed(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].old=0;
}
else
continue;
}
else if(s2-fnode.sign==2)//若在closed表中,则置为old,记下较小的g,并将old从closed表中移出,将较小的g的节点放入closed表中
{
s2-fnode.old=1;
if(s2-fnode.gmaze[s2-fnode.x][s2-fnode.y].g)
{
maze[s2-fnode.x][s2-fnode.y].g=s2-fnode.g;
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
out_closed(maze[s2-fnode.x][s2-fnode.y]);
in_closed(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,则将此节点放入open表中,并计算此节点的f值
{
in_open(maze[s2-fnode.x][s2-fnode.y]);
maze[s2-fnode.x][s2-fnode.y].f=maze[s2-fnode.x][s2-fnode.y].g+maze[s2-fnode.x][s2-fnode.y].h;
}
s2=s2-next;
}
s2=successor;
}
}
else
printf(“error!!This maze does not have the answer!”);
return(0);
}
微信扫一扫 
支付宝扫一扫 
