1 #include2 #include 3 #define error 0 4 #define ok 1 5 #define no 0 6 typedef struct 7 { 8 int i,j; 9 int foot; 10 int mark; 11 }postype; 12 typedef struct 13 { 14 int ord; 15 int di; 16 postype seat; 17 }selemtype; 18 typedef struct snode 19 { 20 selemtype data; 21 struct snode*next; 22 }linkstack; 23 int initstack(linkstack*&s) 24 { 25 s=NULL; 26 return ok; 27 } 28 int push(linkstack *&s,selemtype e) 29 { 30 linkstack *p; 31 p=(linkstack*)malloc(sizeof(linkstack)); 32 p->data=e; 33 p->next=s; 34 s=p; 35 return ok; 36 } 37 int stackempty(linkstack*s) 38 { 39 if(s==NULL) 40 return ok; 41 return no; 42 } 43 int pop(linkstack*&s,selemtype &e) 44 { 45 linkstack*p; 46 if(!s) 47 return error; 48 p=s; 49 e=s->data; 50 s=s->next; 51 free(p); 52 return ok; 53 } 54 linkstack*mazepath(postype maze[11][11],postype start,postype end) 55 { 56 linkstack*s; 57 postype curpos=start; 58 int curstep=1; 59 initstack(s); 60 selemtype e; 61 do 62 { 63 if(curpos.foot&&curpos.mark) 64 { 65 curpos.foot=maze[curpos.i][curpos.j].foot=0; 66 e.ord=curstep; 67 e.seat=curpos; 68 e.di=1; 69 push(s,e); 70 if(curpos.i==end.i&&curpos.j==end.j) 71 return s; 72 curpos=maze[e.seat.i][e.seat.j+1]; 73 curstep++; 74 } 75 else 76 { 77 if(!stackempty(s)) 78 { 79 pop(s,e); 80 while(e.di==4&&!stackempty(s)) 81 { 82 e.seat.mark=0; 83 pop(s,e); 84 } 85 if(e.di<4) 86 { 87 e.di++; 88 push(s,e); 89 if(e.di==1) 90 curpos=maze[e.seat.i][e.seat.j+1]; 91 if(e.di==2) 92 curpos=maze[e.seat.i+1][e.seat.j]; 93 if(e.di==3) 94 curpos=maze[e.seat.i][e.seat.j-1]; 95 if(e.di=4) 96 curpos=maze[e.seat.i-1][e.seat.j]; 97 } 98 } 99 }100 }while(!stackempty(s));101 return no;102 }103 void main()104 {105 postype maze[11][11];106 int i,j;107 linkstack*s;108 selemtype e;109 char a[11][11]=110 {111 { '#','#','#','#','#','#','#','#','#','#'},112 { '#',' ',' ','#',' ',' ',' ','#',' ','#'},113 { '#',' ',' ','#',' ',' ',' ','#',' ','#'},114 { '#',' ',' ',' ',' ','#','#',' ',' ','#'}, 115 { '#',' ','#','#','#',' ',' ',' ',' ','#'}, 116 { '#',' ',' ',' ','#',' ',' ',' ',' ','#'}, 117 { '#',' ','#',' ',' ',' ','#',' ',' ','#'}, 118 { '#',' ','#','#','#',' ','#','#',' ','#'}, 119 { '#','#',' ',' ',' ',' ',' ',' ',' ','#'}, 120 { '#','#','#','#','#','#','#','#','#','#'}121 }; 122 int b[11][11]=123 {124 0,0,0,0,0,0,0,0,0,0, 125 0,0,0,0,0,0,0,0,0,0, 126 0,0,0,0,0,0,0,0,0,0, 127 0,0,0,0,0,0,0,0,0,0, 128 0,0,0,0,0,0,0,0,0,0, 129 0,0,0,0,0,0,0,0,0,0, 130 0,0,0,0,0,0,0,0,0,0, 131 0,0,0,0,0,0,0,0,0,0, 132 0,0,0,0,0,0,0,0,0,0, 133 0,0,0,0,0,0,0,0,0,0,134 };135 printf("原迷宫:\n\n");136 for(i=0;i<10;i++)137 {138 for(j=0;j<10;j++)139 printf("%c ",a[i][j]);140 printf("\n");141 }142 for(i=0;i<=10;i++)143 {144 for(j=0;j<=10;j++)145 {146 maze[i][j].i=i;147 maze[i][j].j=j;148 if(a[i][j]=='#')149 maze[i][j].mark=0;150 else151 maze[i][j].mark=1;152 maze[i][j].foot=1;153 }154 }155 s=mazepath(maze,maze[1][1],maze[8][8]);156 while(!stackempty(s))157 {158 pop(s,e);159 b[e.seat.i][e.seat.j]=1;160 }161 printf("路径:");162 for(i=0;i<10;i++)163 {164 for(j=0;j<10;j++)165 printf("%d ",b[i][j]);166 printf("\n");167 }168 }
1 #include2 #include 3 #include 4 #define TRUE 1 5 #define FALSE 0 6 #define OK 1 7 #define ERROR 0 8 #define OVERFLOW -2 9 typedef int Status; 10 //stack.h 11 //#include "base.h" 12 #define INIT_SIZE 100 //存储空间初始分配量 13 #define INCREMENT 10 //存储空间分配增量 14 typedef struct{ //迷宫中r行c列的位置 15 int r; 16 int c; 17 }PostType; 18 typedef struct{ 19 int ord; //当前位置在路径上的序号 20 PostType seat;//当前坐标 21 int di; //往下一坐标的方向 22 }SElemType; //栈元素类型 23 typedef struct{ 24 SElemType* base;//栈基址,构造前销毁后为空 25 SElemType* top;//栈顶 26 int stackSize; //栈容量 27 }Stack; //栈类型 28 Status InitStack(Stack &S){ //构造空栈s 29 S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType)); 30 if(!S.base) 31 exit(OVERFLOW);//存储分配失败 32 S.top=S.base; 33 S.stackSize=INIT_SIZE; 34 return OK; 35 }//InitStack 36 37 Status StackEmpty(Stack S){ 38 //若s为空返回TRUE,否则返回FALSE 39 if(S.top==S.base) 40 return TRUE; 41 return FALSE; 42 }//StackEmpty 43 44 Status Push(Stack &S,SElemType e){ 45 //插入元素e为新的栈顶元素 46 if(S.top-S.base >=S.stackSize){ //栈满，加空间 47 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType)); 48 if(!S.base) 49 exit(OVERFLOW); //存储分配失败 50 S.top=S.base+S.stackSize; 51 S.stackSize+=INCREMENT; 52 } 53 *S.top++=e; 54 return OK; 55 }//push 56 Status Pop(Stack &S,SElemType &e){ //若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR 57 if(S.top==S.base) 58 return ERROR; 59 e=*--S.top; 60 return OK; 61 }//Pop 62 Status DestroyStack(Stack &S) 63 { //销毁栈S, 64 free(S.base); 65 S.top=S.base; 66 return OK; 67 }//DestroyStack 68 69 //maze.cpp 70 //#include "stack.h" 71 #define MAXLEN 10//迷宫包括外墙最大行列数目 72 typedef struct{ 73 int r; 74 int c; 75 char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' 76 }MazeType; //迷宫类型 77 Status InitMaze(MazeType &maze){ 78 //初始化迷宫若成功返回TRUE,否则返回FALSE 79 int m,n,i,j; 80 printf("Enter row and column numbers: "); 81 scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数 82 for(i=0;i<=maze.c+1;i++){ //迷宫行外墙 83 maze.adr[0][i]='#'; 84 maze.adr[maze.r+1][i]='#'; 85 }//for 86 for(i=0;i<=maze.r+1;i++){ //迷宫列外墙 87 maze.adr[i][0]='#'; 88 maze.adr[i][maze.c+1]='#'; 89 } 90 for(i=1;i<=maze.r;i++) 91 92 for(j=1;j<=maze.c;j++) 93 94 maze.adr[i][j]=' ';//初始化迷宫 95 printf("Enter block's coordinate((-1,-1) to end): "); 96 97 scanf("%d%d",&m,&n);//接收障碍的坐标 98 while(m!=-1){ 99 100 if(m>maze.r || n>maze.c)//越界101 exit(ERROR);102 103 maze.adr[m][n]='#';//迷宫障碍用'#'标记104 printf("Enter block's coordinate((-1,-1) to end): ");105 106 scanf("%d%d",&m,&n);107 108 }//while109 110 return OK;111 112 }//InitMaze 113 114 Status Pass(MazeType maze,PostType curpos){115 116 //当前位置可通则返回TURE,否则返回FALSE117 118 if(maze.adr[curpos.r][curpos.c]==' ')//可通119 return TRUE;120 121 else122 123 return FALSE;124 125 }//Pass126 127 Status FootPrint(MazeType &maze,PostType curpos){128 129 //若走过并且可通返回TRUE,否则返回FALSE130 131 //在返回之前销毁栈S132 133 maze.adr[curpos.r][curpos.c]='*';//"*"表示可通134 return OK;135 136 }//FootPrint137 138 PostType NextPos(PostType &curpos,int i){139 //指示并返回下一位置的坐标140 PostType cpos;141 cpos=curpos;142 switch(i){ //1.2.3.4分别表示东,南,西,北方向143 case 1 : cpos.c+=1; break;144 case 2 : cpos.r+=1; break;145 case 3 : cpos.c-=1; break;146 case 4 : cpos.r-=1; break;147 default: exit(ERROR); 148 }149 return cpos;150 }//Nextpos151 152 Status MarkPrint(MazeType &maze,PostType curpos){153 //曾走过但不是通路标记并返回OK154 maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通155 return OK;156 }//MarkPrint157 158 Status MazePath(MazeType &maze,PostType start,PostType end){159 160 //若迷宫maze存在从入口start到end的通道则求得一条存放在栈中161 //并返回TRUE,否则返回FALSE162 163 Stack S;164 165 PostType curpos;166 167 int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向168 SElemType e;169 170 InitStack(S);171 172 curpos=start; //设置"当前位置"为"入口位置"173 174 curstep=1; //探索第一步175 do{176 177 if(Pass(maze,curpos)){ //当前位置可以通过,178 179 //即是未曾走到过的通道180 FootPrint(maze,curpos);//留下足迹181 e.ord=curstep;182 183 e.seat=curpos;184 185 e.di=1;186 187 Push(S,e); //加入路径188 if(curpos.r==end.r&& curpos.c==end.c)189 190 if(!DestroyStack(S))//销毁失败191 exit(OVERFLOW);192 193 else 194 195 return TRUE; //到达出口196 else{197 198 curpos=NextPos(curpos,1); 199 200 //下一位置是当前位置的东邻201 curstep++; //探索下一步202 }//else203 204 }//if205 206 else{ //当前位置不通207 if(!StackEmpty(S)){208 209 Pop(S,e);210 211 while(e.di==4212 213 && !StackEmpty(S)){214 215 MarkPrint(maze,e.seat);216 217 Pop(S,e); 218 219 //留下不能通过的标记,并退一步220 }//while221 222 if(e.di < 4){223 224 e.di++;//换下一个方向探索225 Push(S,e); 226 227 curpos=NextPos(e.seat,e.di);//设定当前位置是该228 //新方向上的相邻229 }//if230 231 }//if232 233 }//else234 235 }while(!StackEmpty(S));236 237 if(!DestroyStack(S))//销毁失败238 exit(OVERFLOW); 239 240 else 241 242 return FALSE;243 244 }//MazePath245 246 void PrintMaze(MazeType &maze){247 248 //将标记路径信息的迷宫输出到终端(包括外墙)249 250 int i,j;251 252 printf("\nShow maze path(*---pathway):\n\n");253 254 printf(" ");255 256 for(i=0;i<=maze.r+1;i++)//打印列数名257 printf("%4d",i);258 259 printf("\n\n");260 261 for(i=0;i<=maze.r+1;i++){262 263 printf("%2d",i);//打印行名 264 265 for(j=0;j<=maze.c+1;j++)266 267 printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记 268 269 printf("\n\n");270 271 }272 273 }//PrintMaze274 275 276 277 void main(){ //主函数278 MazeType maze;279 280 PostType start,end;281 282 char cmd;283 284 do{285 286 printf("-------FOUND A MAZEPATH--------\n");287 288 if(!InitMaze(maze)){ //初始化并创建迷宫289 printf("\nInitialization errors!!!\n");290 291 exit(OVERFLOW); //初始化错误292 }293 294 do{ //输入迷宫入口坐标295 printf("\nEnter entrance coordinate of the maze: ");296 297 scanf("%d%d",&start.r,&start.c);298 299 if(start.r>maze.r || start.c>maze.c){300 301 printf("\nBeyond the maze!!!\n");302 303 continue;304 305 }306 307 }while(start.r>maze.r || start.c>maze.c);308 309 do{ //输入迷宫出口坐标310 printf("\nEnter exit coordinate of the maze: ");311 312 scanf("%d%d",&end.r,&end.c);313 314 if(end.r>maze.r || end.c>maze.c){315 316 printf("\nBeyond the maze!!!\n");317 318 continue;319 320 }321 322 }while(end.r>maze.r || end.c>maze.c);323 324 if(!MazePath(maze,start,end))//迷宫求解325 printf("\nNo path from entrance to exit!\n");326 327 else328 329 PrintMaze(maze);//打印路径330 printf("\nContinue?(y/n): ");331 332 scanf("%s",&cmd);333 334 }while(cmd=='y' || cmd=='Y');335 336 }//main