maze problem.c

迷宫问题以一个m＊n的长方阵表示迷宫

#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;i<7;i++)
  for(j=0;j<7;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;i<7;i++)//输出迷宫示意图
 {
  for(j=0;j<7;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==6&&bestnode->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==0&&j==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==0&&j==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==6&&j==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==6&&j==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.g<maze[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.g<maze[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);
}