迷宫问题

(一)http://bbs./post-103018.html

几点说明：
１．本程序是动态的，运行后自动寻找迷宫出路
２.有什么不懂的可以在本贴留言．
３.本程序对Ｃ语言刚学完的有很大的意义．
4.四周是墙,坐标(1,1)是入口,右下脚是出口
声明:本程序用VC调试是无法通过的需要修改
     本程序调试工具是TC.....................
     有些同志们抱怨没有注释,有注释就学不到东西了,查阅资料是非常重要的能力.
6.今日特加上注释以供大家学习。
#include "graphics.h"
#include "dos.h"
#include "stdlib.h"
#include "process.h"

#define MAX_COL 14/*定义迷宫大小*/
#define MAX_ROW 14

typedef struct
{ int vert;
  int horiz;
}offsets;


mapture(int i,int j,int k);/*标记迷宫，（i,j）标记为k模式*/
initmaze();/*初始化迷宫数组*/
findmaze(int i,int j);/*找到了（i,j）可走，标记*/
mapmaze();/*画出原始迷宫*/
int findpath(int row,int col);/*递归函数，找出迷宫路径*/
mapbar();/*画出方格*/
initgrap();/*初始化ＶＧＡ*/
print();/*迷宫走完后，输出是否成功 */


int startx=50,starty=50;/*画图的屏幕坐标*/
int maze[MAX_ROW][MAX_COL];
offsets move[8]={{0,1},{1,1},{-1,1},{1,0},{-1,0},{0,-1},{1,-1},{-1,-1}}; /*8个方向寻找*/


initmaze()/*初始化迷宫数组 */
{ int i,j;

  for(i=0;i<MAX_ROW;i++)/*迷宫四周设置为1 代表墙*/
    { maze[i][0]=1;
      maze[i][MAX_COL-1]=1;
     }
  for(i=0;i<MAX_COL;i++)
    {  maze[0][i]=1;
       maze[MAX_ROW-1][i]=1;
     }
     randomize();
  for(i=1;i<MAX_ROW-1;i++)/*迷宫图形随机产生 1表示不通 0表示可行*/
     for(j=1;j<MAX_COL-1;j++)
       {
     maze[i][j]=random(2);
       }

}




findmaze(int i,int j)/*找到 （i,j）可走*/
{
   mapture(j,i,2);/*在图形上标记*/
            sleep(1);



}

returnmaze(int i,int j)/*找到（i,j）可走 ，但下一步无路走则标记*/
{

   mapture(j,i,3);/*在图形上标记*/
   sleep(1);
}

 

print(int i)/*迷宫走完后，输出是否成功*/
{    settextstyle(1,0,5);
    if(i==1)
    outtextxy(340,400,"Ture path!");
    else if(i==2)
    outtextxy(340,400,"No path!");

}

int findpath(int row,int col)/*用递归法找迷宫*/
{  int direct,next_row,next_col;
   direct=0;
   maze[1][1]=2;
   mapture(1,1,2);
   sleep(1);
   while(direct<8)/*8个方向寻找*/
   {  next_row=row+move[direct].vert;/*设置下一步坐标*/
      next_col=col+move[direct].horiz;
      if(maze[next_row][next_col]==0) /*可走，便标记*/
    { maze[next_row][next_col]=2;
          findmaze(next_row,next_col) ;
      if(next_row==(MAX_ROW-2)&&next_col==(MAX_COL-2))/*找到出口退出程序*/
       {  print(1);
              getch();
          exit(0);
       }
      else
        findpath(next_row,next_col);/*没有到出口继续递归*/
      maze[next_row][next_col]=3;
      returnmaze(next_row,next_col);
    }
      direct++;
    }
   return(row);
}

 

(二)http://www./itedu/200707/129098.html

//定义点变量类形
typedef struct
{
int x;
int y;
int z;
} NONCE;

//函数原数
int startpd(NONCE [8][8],NONCE);    //起点判断
NONCE next(NONCE);     //试探下一步函数
void save(NONCE [8][8],NONCE [100],int);  //存档
void load(NONCE [8][8],NONCE [100],int);  //读档
int bjpd(NONCE);             //边界判断
int hfpd(NONCE [8][8],NONCE); //合法点判断

//程序入口
int main()
{
NONCE chess[8][8];   //定义棋盘,行列表示格子,成员x表示棋盘步数,成员z表示下一步将要试探的地方
                     //由于骑士最多只能走八个方向,故z值只能取 0 ~ 7  
int i,j,k;
NONCE start;
   for(i=0;i<8;i++)
     for(j=0;j<8;j++)
      {
 start.x=i;start.y=j;start.z=0;
 if(startpd(chess,start))goto endfor;    //起点判断,如果该点可以为起点则返回1
                                                //否则返回0
      }
endfor:
   //输出
    for(i=0;i<8;i++)
     {
       for(j=0;j<8;j++)
  {
    if(chess[i][j].x==-1)         //骑士没有走的地方显示 "@"
     cout << "@    ";
    else
     printf("%2d   ",chess[i][j].x);  //骑士走过的地方显示所走的是第几步
  }
      cout << endl << endl;
     }
return 0;
} //end main

 

$False$

//起点判断,如果该点可以为起点则返回1
//否则返回0
int startpd(NONCE chess[8][8],NONCE start)
{
NONCE  stack[100];  //定义堆栈
NONCE  nexttmp;
int point;
int i,j,k;

//将棋盘清空
    for(i=0;i<8;i++)
      for(j=0;j<8;j++)
       {
 chess[i][j].x=-1;
 chess[i][j].y=0;
 chess[i][j].z=0;
       }

//将堆栈清空
    for(i=0;i<100;i++)
      {
       stack[i].x=0;
       stack[i].y=0;
       stack[i].z=0;
      }

//将起点赋值给栈底
  point=0;
    stack[point].x=start.x;
    stack[point].y=start.y;
    stack[point].z=start.z;

  do{
    nexttmp=next(stack[point]);   //试探下一步
      if(hfpd(chess,nexttmp))     //判断试探的下一步是否合法
  {
    point++;               //如果合法,则存档 
    stack[point]=nexttmp;
    save(chess,stack,point);  //存档
  }
      else if(stack[point].z<7)   //如果不合法,则判断8种走法是否走完
  {                        //如果没走完,则继续试探下一种走法 
    stack[point].z++;
  }
      else
  {
    point--;               //如果8种走法都走完还是没有出路,则已表示该点
                                  //为死点,退回到上一步继续试探,即像游戏玩家那调档
    load(chess,stack,point);  //读档
    stack[point].z++;
  }

       if(stack[0].z>=8)return 0;   //如果栈底的8种走都已走完，

则表示该点不能作为起点,函数返回0
       cout << "  " << point << endl;
    }while(point<=STP);             //如果已走完指定的步数,退出试探,函数返回1
return 1;
}  //end startpd

//存档函数
void save(NONCE chess[8][8],NONCE  stack[100],int point)
{
int i,j,k;

  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
  for(k=0;k<=point;k++)
    {
      chess[stack[k].x][stack[k].y].x=k;
      chess[stack[k].x][stack[k].y].y=0;
      chess[stack[k].x][stack[k].y].z=stack[k].z;
    }
}  //end save

//读档函数
void load(NONCE chess[8][8],NONCE stack[100],int point)
{
int i,j,k;
  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}
  for(k=0;k<=point;k++)
    {
      chess[stack[k].x][stack[k].y].x=k;
      chess[stack[k].x][stack[k].y].y=0;
      chess[stack[k].x][stack[k].y].z=stack[k].z;
    }
}//end load

//试探下一步点函数
NONCE  next(NONCE  non)
{
NONCE  nex;
begin:
 if(non.z==0)
   {
   nex.x=non.x+2;
   nex.y=non.y-1;
   }
 else if(non.z==1)
   {
   nex.x=non.x+1;
   nex.y=non.y-2;
   }
 else if(non.z==2)
   {
   nex.x=non.x-1;
   nex.y=non.y-2;
   }
 else if(non.z==3)
   {
   nex.x=non.x-2;
   nex.y=non.y-1;
   }
 else if(non.z==4)
   {
   nex.x=non.x-2;
   nex.y=non.y+1;
   }
 else if(non.z==5)
   {
   nex.x=non.x-1;
   nex.y=non.y+2;
   }
 else if(non.z==6)
   {
   nex.x=non.x+1;
   nex.y=non.y+2;
   }

 else if(non.z==7)
   {
   nex.x=non.x+2;
   nex.y=non.y+1;
   }
 nex.z=0;
 if(bjpd(nex))
  {
    non.z++;
    goto begin;
  }
return nex;
} // end   nextpd

//边界判断函数
int bjpd(NONCE nex)
{
if(nex.x<0||nex.x>7||nex.y<0||nex.y>7)
    return 1;
else
    return 0;
}//end bjpd

//合法点判断函数
int hfpd(NONCE chess[8][8],NONCE non)
{
if(chess[non.x][non.y].x==-1)
   return 1;
else
   return 0;
} // end nextpd

 

 

 

(三)http://www./html/developer/cc/20070325/11431.html

/*============================================================
  钻迷宫<2.0>
  迷宫用二维数组存储;
  迷宫随机生成;
  前进方向只有四个,就是上下左右;
  用栈存储走过的路,碰壁可以返回;
  TC2.0下编译通过!
  ============================================================*/
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define UP 1   /*用于存储方向的常量*/
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define OK 0
#define ERROR -1

struct  maze{
 int left;
 int top;
 int right;
 int bottom;
 int sign; /*记号(0表示空白,1表示墙,2表示走过的路,3表示走过并且返回的路,4老鼠所在位置)*/
}lab[22][42];/*定义迷宫存储结构*/

typedef struct SNode{
 int data;
 struct SNode *next;
}SNode;

typedef struct {
 int length;
 SNode *top;
}STACK;/*定义存储走过路线的栈*/

/*栈初始化*/
void InitStack(STACK *S)
{
 S->top=NULL;
 S->length=NULL;
}

/*元素e入栈*/
int Push(STACK *S,int e)
{
 SNode *p;
 p=(SNode *)malloc(sizeof(SNode));
 if(!p) return ERROR;
 p->data=e;
 p->next=S->top;
 S->top=p;
 S->length++;
 return OK;
}

/*栈顶元素出栈,e带回栈顶元数*/
int Pop(STACK *S,int *e)
{
 SNode *p;
 if(S->top==NULL) return ERROR;
 p=S->top;
 *e=p->data;
 S->top=p->next;
 S->length--;
 free(p);
 return OK;
}
/*判断S是否为空栈*/
int Empty(STACK S)
{
 if(S.top==NULL) return OK;
 return ERROR;
}

/*初始化图形显示*/
int initialize(void)
{
    int gdriver, gmode,errorcode;
    gdriver=VGA;
    gmode=VGAHI;
    initgraph(&gdriver, &gmode, "d:\c源码");
    errorcode = graphresult();
    if (errorcode != grOk)  /* an error occurred */
   {
      printf("Graphics error: %s\n", grapherrormsg(errorcode));
      printf("Press any key to halt:");
      getch();
      exit(1);             /* return with error code */
   }
   return 0;
}

void showmaze(int i,int j)
{/*显示迷宫函数*/
  switch(lab[i][j].sign)
  {
   case 0: setfillstyle(SOLID_FILL,LIGHTBLUE);break;
   case 1: setfillstyle(SOLID_FILL,MAGENTA); break;
   case 2: setfillstyle(SOLID_FILL,GREEN);break;
   case 3: setfillstyle(SOLID_FILL,DARKGRAY);break;
   case 4: setfillstyle(SOLID_FILL,BLUE);break;
  }
  bar(lab[i][j].left,lab[i][j].top,lab[i][j].right,lab[i][j].bottom);
}

/*生成迷宫函数*/
void initialmaze()
{
 int i,j,n,leftx=100,topy=50,rightx=110,bottomy=60;
 srand((int)time(0));
 for(i=0;i<22;i++)/*随机成生迷宫*/
  for(j=0;j<42;j++)
  {
   lab[i][j].left=leftx+j*10;
   lab[i][j].top=topy+i*10;
   lab[i][j].right=rightx+j*10;
   lab[i][j].bottom=bottomy+i*10;
   n=rand()%20;
   if(n<5)
   lab[i][j].sign=1;
   else
   lab[i][j].sign=0;  
  }
 for(i=0;i<42;i++)/*成生迷宫四周*/
 {
  lab[0][i].sign=1;
  lab[21][i].sign=1;
 }
 for(i=0;i<22;i++)/*成生迷宫四周*/
 {
  lab[i][0].sign=1;
  lab[i][41].sign=1;
 }
 lab[1][0].sign=0;/*为迷宫留入口及出口*/
 lab[1][1].sign=0;
 lab[1][2].sign=0;
 lab[20][41].sign=0;
 lab[20][40].sign=0;
 lab[20][39].sign=0;
 for(i=0;i<22;i++)/*随机成生迷宫*/
  for(j=0;j<42;j++)
    showmaze(i,j);
}

int main(void)
{
 int i,j,way;
 char flag='0';
 STACK S;/*定义一个用于存储老鼠走过的路线的栈*/
 initialize();/*初始化图形显示*/
 InitStack(&S);/*初始化栈*/
 setbkcolor(LIGHTBLUE);/*设置背景色*/
    setcolor(MAGENTA);/*设置前景色*/
 initialmaze();/*成生迷宫*/
 i=1;/*初始化老鼠位置*/
 j=0;
 lab[i][j].sign=4;
 showmaze(i,j);/*显示迷宫*/
 setfillstyle(SOLID_FILL,BLUE);
 bar(120,300, 480, 350);
 moveto(130,310);
 outtext("1.QUICK    2.SLOW");
 moveto(130,330);
 outtext("Chooses 1 or 2");
 while(flag!='1' && flag!='2') flag=getche();
 bar(120,300, 480, 350);
 moveto(130,320);
 if(flag=='2')
 outtext("You Chooses 2.SLOW");
 do{
  lab[i][j].sign=2;
  showmaze(i,j);
  if(lab[i][j+1].sign==0)/*RIGHT*/
  {
   j++;
   Push(&S,RIGHT);
  }
  else if(lab[i+1][j].sign==0)/*DOWN*/
  {
   i++;
   Push(&S,DOWN);
  } 
  else if(lab[i][j-1].sign==0)/*LEFT*/
  {
   j--;
   Push(&S,LEFT);
  }
  else if(lab[i-1][j].sign==0)/*UP*/
  {
   i--;
   Push(&S,UP);
  }
  else /*没路*/
  {
   if(Empty(S)==OK) /*已经退回起点*/
   {
    setfillstyle(SOLID_FILL,BLUE);
    bar(120,300, 480, 350);
    moveto(130,310);
    outtext("The labyrinth does not have the outlet!");
    moveto(130,330);
    outtext("Press any key to exit...");
    getche();
    exit(1);
   }
   else/*返回一步*/
   {
    Pop(&S,&way);
    lab[i][j].sign=3;
    showmaze(i,j);
    switch(way)
    {
     case RIGHT:j--;break;
     case DOWN:i--;break;
     case LEFT:j++;break;
     case UP:i++;break;
    }
   }
  }
  lab[i][j].sign=4;
  showmaze(i,j);/*显示迷宫*/
  if(flag=='2')
  {
   delay(90000);
   sound(700); 
      delay(10000); 
      nosound();
  }
 }while(i!=20 || j!=41);/*走到出口*/
 setfillstyle(SOLID_FILL,BLUE);
 bar(120,300, 480, 350);
 moveto(130,310);
 outtext("Found a road!");
 moveto(130,330);
 outtext("Press any key to exit...");
    getche();
    closegraph();/*关闭图形显示*/
    return 0;
}

 

 

 

 

 

(四)http://www./cavenaghi/archive/2005/07/27/8537.html

迷宫文件boya.ice：

8
9
#########
#s0##0###
#0##00###
#0##0####
#0000####
#0##0####
#0##00e##
#0000####

 

package maze;
import java.io.*;
import java.util.*;
public class Maze{
 private char[][] maze;//迷宫数组
 private int startX,startY,endX,endY;//迷宫起点，终点的位置
 private int x,y,step=0;//迷宫长宽及步骤
 //依据输入的文件名创建对象
 private Maze(String fileName){
  try{
   LinkedList aList=new LinkedList();//用于存储文件每行的内容
   BufferedReader files=new BufferedReader(new FileReader("map\\"+fileName));
   //将每行的内容依次加入到LinkedList中
   String temp=new String();
   int i=0;
   while((temp=files.readLine())!=null){
    aList.add(temp);
   }
   files.close();
   //读取并设置迷宫的长宽
   x=Integer.parseInt((String)aList.getFirst())+2;
   aList.removeFirst();
   y=Integer.parseInt((String)aList.getFirst())+2;
   aList.removeFirst();
   //依据长宽对迷宫进行初始化
   maze=new char[x][y];
   //将迷宫的赋予外围墙
   for(i=0;i<x;i++){
    maze[i][0]='#';
    maze[i][y-1]='#';
   }
   for(i=0;i<y;i++){
    maze[0][i]='#';
    maze[x-1][i]='#';
   }
   //将LinkedList中内容读入数组
   Iterator it=aList.iterator();
   i=1;
   char[] row;
   while(it.hasNext()){
    temp=((String)it.next());
    row=new char[y-2];
    row=temp.toCharArray();
    for(int j=1;j<y-1;j++){
     maze[i][j]=row[j-1];
     if(maze[i][j]=='s'){
      startX=i;
      startY=j;
      maze[i][j]='0';
     }
     else if(maze[i][j]=='e'){
      endX=i;
      endY=j;
      maze[i][j]='0';
     }
    }
    i++;
   }
  }
  catch(FileNotFoundException e){
   System.out.println("File Name Input Wrong!!!");
  }
  catch(IOException e){
   System.out.println("Wrong Input!!!");
  }
 }
 //递归方法寻找路径
 private boolean findWay(int x,int y){
  if(maze[endX][endY]=='i')
   return true;
  else
   if(maze[x][y]=='0'){
    maze[x][y]='i';
    if(findWay(x-1,y))
     return true;
    else if(findWay(x+1,y))
     return true;
    else if(findWay(x,y+1))
     return true;
    else if(findWay(x,y-1))
     return true;
    else{
     maze[x][y]='c';
     return false;
    }
   }
   else return false;
 }
 //打印迷宫路径
 private void show(){
  maze[startX][startY]='s';
  maze[endX][endY]='e';
  for(int i=1;i<x-1;i++){
   for(int j=1;j<y-1;j++){
    if(maze[i][j]=='i'){
     maze[i][j]=' ';
     step++;
    }
    else if(maze[i][j]=='c') maze[i][j]='0';
    System.out.print(maze[i][j]);
   }
   System.out.println("");
  }
  System.out.println("I Have went "+step+" Steps To The End!");
 }
 public static void main(String arg[]){
  try{
   System.out.println("Boya(8*9)\n"+"Ice(10*12)\n"+"Sky(15*17)\n"+"Input the map name:");
   BufferedReader is=new BufferedReader(new InputStreamReader(System.in));
   for(;;){
    String input=new String();
    input=is.readLine().trim();
    if(input.equals("q")) break;
    else{
     Maze boya=new Maze(input+".ice");
     if(boya.findWay(boya.startX,boya.startY)){
      boya.show();
     }
     else System.out.println("No Ways to the end!");
    }
    System.out.println("Input another map name or input 'q' to quit:");
   }
   is.close();
  }
  catch(IOException e){
   System.out.println("Wrong Input!!!");
  }
  catch(NullPointerException e){
   System.out.println("Wrong Input!!!");
  }
 }
}