哥们
----------------解决方案--------------------------------------------------------
看看一个算法应该拆不多
----------------解决方案--------------------------------------------------------
你是一下用矩阵来做这个题目！
我好像看过这个类型的题目！
----------------解决方案--------------------------------------------------------
我一个师弟做的，但愿你用的上。注：编译环境为Turbo C2.0 #include <stdio.h> #include <stdlib.h> #include <graphics.h> #include <time.h> #include <conio.h>
#define MAXSIZE 20
typedef struct { int x; int y; }PosType; typedef struct { int di1; int di2; int di3; int di4; }Direct;
typedef int MazeElem; typedef struct { MazeElem color[MAXSIZE+2][MAXSIZE+2]; PosType start; PosType end; }MazeType;
MazeType mazes; int unit,rows,columns,ratio; PosType offset;
PosType NextPos( PosType curpos,int di) { switch(di) { case 1: curpos.y++;break; case 2: curpos.x++;break; case 3: curpos.y--;break; case 4: curpos.x--;break; } return curpos; }
void Near(PosType start,PosType end) { int i=0; PosType curpos; while(++i<=4) { curpos=NextPos(start,i); if(curpos.x==end.x && curpos.y==end.y) { printf(" success!\n"); getch(); closegraph(); exit(0); } } }
void direction(Direct *direct,PosType start,PosType end) { if(start.y<=end.y) { if(start.x<=end.x) { if(end.y-start.y<=end.x-start.x) { direct->di1=2;direct->di2=1;direct->di3=3;direct->di4=4; } else { direct->di1=1;direct->di2=2;direct->di3=3;direct->di4=4; } } else { if(end.y-start.y<=start.x-end.x) { direct->di1=4;direct->di2=1;direct->di3=3;direct->di4=2; } else { direct->di1=1;direct->di2=4;direct->di3=3;direct->di4=2; } } } else { if(start.x<=end.x) { if(start.y-end.y<=end.x-start.x) { direct->di1=2;direct->di2=3;direct->di3=1;direct->di4=4; } else { direct->di1=3;direct->di2=2;direct->di3=4;direct->di4=1; } } else { if(start.y-end.y<=start.x-end.x) { direct->di1=4;direct->di2=3;direct->di3=1;direct->di4=2; } else { direct->di1=3;direct->di2=4;direct->di3=2;direct->di4=1; } } } } void CreateMaze() { int i,j; clrscr(); printf("\n ********this program is designed by …….********\n black square denotations unpassable; white square denotations passable.\n ratio means white squares:black squares,advised value is 2 or 3. \n define the maze rows,columns and ratio,using {rows,columns,ratio}\n for example {10,20,3}:"); scanf("{%d,%d,%d}",&rows,&columns,&ratio); if(!rows||!columns||!ratio) { rows=20;columns=20;ratio=2;} else if(rows>MAXSIZE || rows<1 || columns>MAXSIZE ||columns<1) { printf(" attention! 1<=rows<=MAXSIZE,1<=columns<=MAXSIZE,MAXSIZE is defined 20\n"); getch(); exit(0); } for(i=0;i<=MAXSIZE+1;i++) for(j=0;j<=MAXSIZE+1;j++) mazes.color[i][j]=BLACK; for(i=1;i<=rows;i++) for(j=1;j<=columns;j++) if(rand()%(ratio+1)) mazes.color[i][j]=WHITE;
scanf("%c",&i);
}
void PointColor(PosType curpos) { setcolor(GREEN); setfillstyle(SOLID_FILL,mazes.color[curpos.y][curpos.x]); bar((curpos.x+offset.x)*unit,(curpos.y+offset.y)*unit,(curpos.x+offset.x+1)*unit,(curpos.y+offset.y+1)*unit); rectangle((curpos.x+offset.x)*unit,(curpos.y+offset.y)*unit,(curpos.x+offset.x+1)*unit,(curpos.y+offset.y+1)*unit); }
void DrawMaze() { int i,j,k,m,n; int gdriver, gmode; PosType curpos; detectgraph(&gdriver, &gmode); registerbgidriver(EGAVGA_driver); /*registerbgidriver(ATT_driver); registerbgidriver(CGA_driver); registerbgidriver(IBM8514_driver); registerbgidriver(PC3270_driver);*/ initgraph(&gdriver, &gmode, "c:\\tc"); setbkcolor(BLACK); m=getmaxx(); n=getmaxy(); k=(m>n?n:m); unit=k/(MAXSIZE*2); m=m/unit; n=n/unit; offset.x=m/4; offset.y=n/4; for(i=1;i<=rows;i++) for(j=1;j<=columns;j++) { curpos.x=j; curpos.y=i; PointColor(curpos);
} printf("\n red square denotations maze start;yellow square denotations maze end.\n define maze start and end using (rowth,columnth).\n for example (2,3),(7,8) : "); scanf("(%d,%d),(%d,%d)",&mazes.start.y,&mazes.start.x,&mazes.end.y,&mazes.end.x); if(!mazes.start.y||!mazes.start.y||!mazes.end.y||!mazes.end.x) { mazes.start.y=1;mazes.start.x=8;mazes.end.y=8;mazes.end.x=19;} else if(mazes.start.x<1||mazes.start.x>columns||mazes.start.y<1||mazes.start.y>rows||mazes.end.x<1||mazes.end.x>columns||mazes.end.y<1||mazes.end.y>rows) { printf(" attention! 1<=x<=rows,1<=y<=columns, you define rows=%d,columns=%d",rows,columns); getch(); exit(0); } mazes.color[mazes.start.y][mazes.start.x]=RED; PointColor(mazes.start); sleep(1); mazes.color[mazes.end.y][mazes.end.x]=YELLOW; PointColor(mazes.end); sleep(1); i=0; while(++i<=4) { curpos=NextPos(mazes.end,i); if(mazes.color[curpos.y][curpos.x]==WHITE) break; } if(i==5) { printf(" maze end unpassable!\n"); getch(); exit(0); } }
void MazePath(PosType start,PosType end) { Direct direct; if(start.x==end.x && start.y==end.y) { printf(" success!\n"); getch(); closegraph(); exit(0); } if(mazes.color[start.y][start.x]==RED ||mazes.color[start.y][start.x]==WHITE) { if(mazes.color[start.y][start.x]==WHITE) { mazes.color[start.y][start.x]=BLUE; PointColor(start); sleep(1); } Near(start,end); direction(&direct,start,end); MazePath(NextPos(start,direct.di1),end); MazePath(NextPos(start,direct.di2),end); MazePath(NextPos(start,direct.di3),end); MazePath(NextPos(start,direct.di4),end); if(mazes.color[start.y][start.x]!=RED) { mazes.color[start.y][start.x]=DARKGRAY; PointColor(start); sleep(1); }
} }
main() { CreateMaze(); DrawMaze(); MazePath(mazes.start,mazes.end); printf(" failed!\n"); getch(); closegraph(); }
----------------解决方案--------------------------------------------------------
用一个栈 加上函数嵌套(我不记得叫什么方法了) 很容易可以出来的
记得以前做了一个不过迷宫是我预先设置好的
----------------解决方案--------------------------------------------------------
hao
----------------解决方案--------------------------------------------------------