迷宫问题
描述： 迷宫问题
迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径.
输入： 迷宫宽度w 迷宫高度h
迷宫第一行
迷宫第二行
...
迷宫第h 行
输出： 入口横坐标1 入口纵坐标1
横坐标2 纵坐标2
横坐标3 纵坐标3
横坐标4 纵坐标4
...
横坐标n-1 纵坐标n-1
出口横坐标n 出口纵坐标n
输入样例： 8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
输出样例： 3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4
[解决办法]
#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define DOWN 1#define LEFT 2#define UP 3#define RIGHT 4#define INITSTACKSIZE 100#define INCREMENTSIZE 10#define MARK 5#define BLIND_ALLEY 6typedef int ** MazeType;MazeType Maze;int Maze_Line,Maze_Column;typedef struct{ int x; int y;} PosType,*PtrtoPos;PtrtoPos start,end;typedef struct{ int ord; PosType seat; int direction;} Record,*PtrtoRecord;typedef struct{ PtrtoRecord base; int top; int stacksize; int length;} SqStack,*PtrtoStack;MazeType CreatMaze(void);PtrtoStack MazePath(MazeType maze,PtrtoPos start,PtrtoPos end);void Print_Path(PtrtoStack path);PtrtoStack InitStack(void);void Push(PtrtoStack ,PtrtoRecord );void Pop(PtrtoStack ,PtrtoRecord );void FootPrint(PtrtoPos );void NextPos(PtrtoPos ,int );void MarkPrint(PtrtoRecord );int StackEmpty(PtrtoStack);void DestroyStack(PtrtoStack);int Pass(PtrtoPos);void FreeMaze(MazeType);int main(){ PtrtoStack Path; Maze=CreatMaze(); Path=MazePath(Maze,start,end); Print_Path(Path); DestroyStack(Path); FreeMaze(Maze); return 0;}MazeType CreatMaze(void){ start=(PtrtoPos)malloc(sizeof(PosType)); end=(PtrtoPos)malloc(sizeof(PosType)); int i,x,y; scanf("%d%d",&Maze_Column,&Maze_Line); MazeType maze; maze=(MazeType)malloc(sizeof(int *)*Maze_Line); for(i=0; i<Maze_Line; i++) maze[i]=(int *)malloc(sizeof(int)*Maze_Column); for(y=0; y<Maze_Line; y++) for(x=0; x<Maze_Column; x++) { scanf("%d",&maze[y][x]); if(maze[y][x]==3) { start->x=x; start->y=y; } if(maze[y][x]==4) { end->x=x; end->y=y; } } return maze;}PtrtoStack MazePath(MazeType Maze,PtrtoPos start,PtrtoPos end){ int curstep=1; PtrtoPos curpos; PtrtoRecord e; PtrtoStack Path; curpos=(PtrtoPos)malloc(sizeof(PosType)); e=(PtrtoRecord)malloc(sizeof(Record)); curpos->x=start->x; curpos->y=start->y; Path=InitStack(); do { if(Pass(curpos)) //当前位置可以通过 { FootPrint(curpos); //留下足迹 e->ord=curstep; e->seat.x=curpos->x; e->seat.y=curpos->y; e->direction=DOWN; Push(Path,e); //加入路径 if(curpos->x==end->x&&curpos->y==end->y) return Path; //到达出口 NextPos(curpos,DOWN); //下一位置变为当前位置 curstep++; } else //当前位置不可通 { if(!StackEmpty(Path)) { Pop(Path,e); while(e->direction==RIGHT&&!StackEmpty(Path)) { MarkPrint(e); Pop(Path,e); } if(e->direction<RIGHT) { e->direction++; Push(Path,e); curpos->x=Path->base[Path->top-1].seat.x; curpos->y=Path->base[Path->top-1].seat.y; NextPos(curpos,e->direction); } } } } while(!StackEmpty(Path)); return 0;}PtrtoStack InitStack(void){ PtrtoStack p; p=(PtrtoStack)malloc(sizeof(SqStack)); p->base=(PtrtoRecord)malloc(sizeof(Record)*INITSTACKSIZE); p->top=0; p->stacksize=INITSTACKSIZE; p->length=0; return p;}void Push(PtrtoStack Path,PtrtoRecord e){ if(Path->length>=Path->stacksize) { Path->base=(PtrtoRecord)realloc(Path->base,sizeof(Record)*(Path->stacksize+INCREMENTSIZE)); Path->stacksize+=INCREMENTSIZE; if(!(Path->base)) { printf("error\n"); exit(0); } } Path->base[Path->top].ord=e->ord; Path->base[Path->top].seat.x=e->seat.x; Path->base[Path->top].seat.y=e->seat.y; Path->base[Path->top].direction=e->direction; Path->top++; Path->length++;}void Pop(PtrtoStack Path,PtrtoRecord e){ if(StackEmpty(Path)) { printf("Empty Stack\n"); exit(0); } Path->top--; e->ord=Path->base[Path->top].ord; e->seat.x=Path->base[Path->top].seat.x; e->seat.y=Path->base[Path->top].seat.y; e->direction=Path->base[Path->top].direction;}void FootPrint(PtrtoPos point){ Maze[point->y][point->x]=MARK;}void NextPos(PtrtoPos curpos,int direction){ switch(direction) { case DOWN : curpos->y++; break; case LEFT : curpos->x--; break; case UP : curpos->y--; break; case RIGHT : curpos->x++; break; }}void MarkPrint(PtrtoRecord e){ Maze[e->seat.y][e->seat.x]=BLIND_ALLEY;}int Pass(PtrtoPos point){ if(Maze[point->y][point->x]==0||Maze[point->y][point->x]==3||Maze[point->y][point->x]==4) return 1; else return 0;}void Print_Path(PtrtoStack Path){ if(Path==NULL) { printf("no path\n"); exit(0); } int i=0; for(; i<Path->top; i++) printf("%d %d\n",Path->base[i].seat.x,Path->base[i].seat.y);}void DestroyStack(PtrtoStack Path){ free(Path->base); free(Path);}int StackEmpty(PtrtoStack Path){ if(Path->top==0) return 1; else return 0;}void FreeMaze(MazeType Maze){ int i; for(i=0;i<Maze_Line;i++) free(Maze[i]); free(Maze);}