Algorithm 版 (精华区)

发信人: ssos (存在与虚无·英雄无敌), 信区: Algorithm
标  题: [合集]请教一下走迷宫的程序问题:)
发信站: 哈工大紫丁香 (2002年01月24日08:46:24 星期四), 站内信件


────────────────────────────────────────
 yuanyin (媛鹰)                       于 Fri Nov 16 14:39:14 2001) 说道:

  小弟才开始学程序编写,想请教一个比较常见的问题.
有一个8*8的表格,任意给出起点和终点坐标(不重合),
要求从起点走到重点,必须不能重复,但是要所有的位置
都要走到,用c语言实现.
  我建立一个二维的数组,走不通返回的办法,但是返回
到上一个节点的时候,不知道怎么把程序接着走另外一个
分支开始循环.
  哪位大哥给一个程序看看好么?谢谢了!

────────────────────────────────────────
 Lerry (Lerry)                        于 2001年11月16日15:33:07 星期五 说道:

但是有时候不是所有的点都能走到

────────────────────────────────────────
 yuanyin (媛鹰)                       于 Fri Nov 16 18:32:15 2001) 说道:

是可能会出现无解的情况.

 分支开始循环.



────────────────────────────────────────
 Lerry (Lerry)                        于 2001年11月16日18:40:17 星期五 说道:

递归

────────────────────────────────────────
 linghan (aoni)                       于 Fri Nov 16 22:03:05 2001) 说道:



#include "conio.h"
#include "stdio.h"
#include "alloc.h"
#include "graphics.h"
int p[150]=  {0,0,0,0,0,1,0,1,1,0,1,1,1,1,1,
      1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,
      1,1,1,1,1,1,0,0,1,0,1,1,0,1,1,
      0,1,0,1,1,0,0,1,1,0,1,0,1,1,1,
      1,0,1,0,0,1,1,1,1,1,1,1,1,0,1,
      0,1,0,1,1,1,0,1,1,0,1,1,0,1,1,
      0,0,1,1,1,0,0,0,0,1,0,1,1,0,1,
      1,0,0,1,1,1,1,0,1,1,1,0,1,1,1,
      0,1,1,0,0,1,0,1,1,1,1,1,0,1,1,
      1,0,1,1,1,0,1,1,1,0,0,0,0,0,0} ;

printfstar()
{printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * \n\n");
 printf("* * * * * * * * * * *MAZE * * * * * * * * * * * * * * * \n\n");     }

message()
{int driver,gmode;
 driver=DETECT;
 gmode=0;
  initgraph(&driver,&gmode," ");
  setcolor(12);}
main()
{ clrscr();
  printfstar();
/*  message();           */
  way(p,10,15);
  display(p);
  getch();
}

 int way(int p[],int m,int n)
{ int i,j,v,g,h,flag;
  int *pi,*pj,*stack,*top;

  pi=malloc(8*sizeof(int));
  if(pi==NULL) {printf("Allocation is failed (*pi).");exit(1);}
  pj=malloc(8*sizeof(int));
    if(pj==NULL) {printf("Allocation is failed (*pj).");exit(1);}
  stack=malloc(200*sizeof(int));
    if(stack==NULL) {printf("Allocation is failed (*stack).");exit(1);}
  top=stack;

  pi[0]=0;pi[1]=1;pi[2]=1;pi[3]=1;
  pi[4]=0;pi[5]=-1;pi[6]=-1;pi[7]=-1;
  pj[0]=1;pj[1]=1;pj[2]=0;pj[3]=-1;
  pj[4]=-1;pj[5]=-1;pj[6]=0;pj[7]=1;
  i=0;j=0;v=0;
  p[0]=4;
do
{g=i+pi[v];h=j+pj[v];flag=0;
 if((g>-1)&&(g<m)&&(h>-1)&&(h<n))
  {
      if( (p[(m-1)*n+n-1]==0) && (g==m-1) && (h==n-1) )
      {p[i*n+j]=8;p[g*n+h]=8; break;}

    if(p[g*n+h]==0)
      {p[g*n+h]=4;
       p[i*n+j]=8;
       top=top+3;
       top[0]=i;top[1]=j;top[2]=v;
       i=g;j=h;v=0;flag=1; }
   }
 if(flag==0)
   { if(v<7)        v=v+1;
     else
     {while((top!=stack)&&(top[2]==7))
       {p[top[0]*n+top[1]]=4;
top=top-3;
  if(top!=stack)
   {i=top[0];j=top[1];v=top[2];
     p[i*n+j]=4;top=top-3;  }
}
      }
    } /*END IF*/

 } while(top!=stack||v!=7);
   free(pi); free(pj); free(stack);
}

display(int p[])
{int i,j;
 if(p[0]==4) printf(" \n There is no EXIT\n ");
 else{ printf("The path is * :\n\n");
       for(i=0;i<150;i++)
       {  if(p[i]==8)
  { textcolor(174);
    cprintf(" *");
    }
    else if (p[i]==1)
    { textcolor(12);
      cprintf(" !");
     }
    else
     { textcolor(10);
       cprintf(" %d",p[i]);
     }
    if((i+1)%15==0) printf("\n");
  }
       }
  printf("\n\n");
  printf("END\n");
  }









试看吧。未必行，看运气吧！！！


────────────────────────────────────────