acm.rar_acm经典题目

#include<iostream> #include<malloc.h> #include<stdlib.h> using namespace std; #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -2 typedef int Status; typedef char ElemType; typedef struct { int x; int y; }PosType; typedef struct { int ord; PosType seat; int di; }SElemType; typedef struct { SElemType *base,*top; int stacksize; }SqStack; Status InitStack(SqStack &s) { s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK; } Status Push(SqStack &s,SElemType e) { if(s.top-s.base==s.stacksize) { s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s.base) exit(OVERFLOW); s.stacksize+=STACKINCREMENT; } s.top->ord=e.ord; s.top->seat=e.seat; s.top->di=e.di; s.top++; return OK; } Status Pop(SqStack &s,SElemType &e) { if(s.base==s.top) return ERROR; s.top--; e.ord=s.top->ord; e.seat=s.top->seat; e.di=s.top->di; return OK; } Status Pass(int (&maze)[10][10],PosType curpos) { if (maze[curpos.x][curpos.y]==0) return 1; // 如果当前位置是可以通过，返回1 else return 0; // 其它情况返回0 } void FootPrint(int (&maze)[10][10],PosType curpos) //标记走过的 { maze[curpos.x][curpos.y]=-1; } void MarkPrint(int (&maze)[10][10],PosType curpos) { //取消标记 maze[curpos.x][curpos.y]=0; } void NextPos(PosType &pos, int di) //下一个方向 { switch(di) { case 1: (pos).y+=1; break; //向东 case 2: (pos).x+=1; break; //向南 case 3: (pos).y-=1; break; //向西 case 4: (pos).x-=1; break; //向北 } } Status StackEmpty(SqStack s) //判断栈空 { if(s.top==s.base) return true; else return false; } Status MazePath(int (&maze)[10][10],PosType start,PosType end) //走迷宫 { SqStack S; PosType curpos=start; int curstep=1; SElemType e; InitStack(S); do { if(Pass(maze,curpos)) { FootPrint(maze,curpos); e.ord = curstep; e.seat= curpos; e.di =1; Push(S,e); if(curpos.x==end.x&&curpos.y==end.y) return true; NextPos(curpos, 1); curstep++; } else { if (!StackEmpty(S)) { while(e.di==4&&!StackEmpty(S)) { Pop(S,e); MarkPrint(maze,e.seat); } Pop(S,e); if(e.di<4) { e.di++; Push (S,e); NextPos(e.seat, e.di); curpos=e.seat; } } } } while(!StackEmpty(S)); return false; } void Print(int maze[10][10]) //输出迷宫，路径用*标出，墙壁用#,可通过的地方用空格 { for(int i=0;i<10;i++) { for(int j=0;j<10;j++) if(maze[i][j]==0) cout<<" "; else if(maze[i][j]==-1) cout<<"*"; else cout<<"#"; cout<<endl; } cout<<endl; } int main() { int m[10][10]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; Print(m); PosType start,end; start.x=start.y=1; end.x=end.y=8; if(MazePath(m,start,end)) Print(m); return 0; }