中财网名创优品压缩面膜:迷宫问题
来源：百度文库 编辑：中财网 时间：2024/04/29 19:50:11
１．本程序是动态的，运行后自动寻找迷宫出路
２.有什么不懂的可以在本贴留言．
３.本程序对Ｃ语言刚学完的有很大的意义．
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
maze[i][MAX_COL-1]=1;
}
for(i=0;i
maze[MAX_ROW-1][i]=1;
}
randomize();
for(i=1;i
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.xue5.com/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.oklinux.cn/html/developer/cc/20070325/11431.html
(四)http://www.blogjava.net/cavenaghi/archive/2005/07/27/8537.html/*============================================================
钻迷宫<2.0>
迷宫用二维数组存储;
迷宫随机生成;
前进方向只有四个,就是上下左右;
用栈存储走过的路,碰壁可以返回;
TC2.0下编译通过!
============================================================*/
#include
#include
#include
#include
#include
#define UP 1 /*用于存储方向的常量*/
#define DOWN 2
#define LEFT 3
#define RIGHT 4
#define OK 0
#define ERROR -1struct 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;
}
迷宫文件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
maze[i][y-1]='#';
}
for(i=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
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
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!!!");
}
}
}