当前位置： 代码迷 >> C语言 >> [求助]一个迷营算法
  详细解决方案

[求助]一个迷营算法

热度：309   发布时间：2006-05-14 14:41:00.0
[求助]一个迷营算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;


#define INIT_SIZE 100
#define INCREMENT 10
typedef struct{
int r;
int c;
}PostType;
typedef struct{
int ord;
PostType seat;
int di;
}SElemType;
typedef struct{
SElemType* base;
SElemType* top;
int stackSize;
}Stack;
Status InitStack(Stack S){
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}
Status StackEmpty(Stack S){

if(S.top==S.base)
return TRUE;
return FALSE;
}
Status Push(Stack S,SElemType e){

if(S.top-S.base >=S.stackSize){
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(Stack S,SElemType e){
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status DestroyStack(Stack S){
free(S.base);
S.top=S.base;
return OK;
}

#define MAXLEN 10
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];
}MazeType;
Status InitMaze(MazeType maze){

int m,n,i,j;
printf("Enter row and column numbers: ");
scanf("%d,%d",&maze.r,&maze.c);
for(i=0;i<=maze.c+1;i++){
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}
for(i=0;i<=maze.r+1;i++){
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d,%d",&m,&n);
while(m!=-1){
if(m>maze.r || n>maze.c)
exit(ERROR);
maze.adr[m][n]='#';
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d,%d",&m,&n);
}
return OK;
}
Status Pass(MazeType maze,PostType curpos){

if(maze.adr[curpos.r][curpos.c]==' ')
return TRUE;
else
return FALSE;
}
Status FootPrint(MazeType maze,PostType curpos){


maze.adr[curpos.r][curpos.c]='*';
return OK;
}
PostType NextPos(PostType curpos,int i){

PostType cpos;
cpos=curpos;
switch(i){
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
return cpos;
}
Status MarkPrint(MazeType maze,PostType curpos){

maze.adr[curpos.r][curpos.c]='@';
return OK;
}
Status MazePath(MazeType maze,PostType start,PostType end){

Stack S;
PostType curpos;
int curstep;
SElemType e;
InitStack(S);
curpos=start;
curstep=1;
do{
if(Pass(maze,curpos)){

FootPrint(maze,curpos);
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e);
if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))
exit(OVERFLOW);
else
return TRUE;
else{
curpos=NextPos(curpos,1);

curstep++;
}
}
else{
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4
&& !StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e);

}
if(e.di < 4){
e.di++;
Push(S,e);
curpos=NextPos(e.seat,e.di);

}
}
}
}while(!StackEmpty(S));
if(!DestroyStack(S))
exit(OVERFLOW);
else
return FALSE;
}
void PrintMaze(MazeType maze){

int i,j;
printf("\nShow maze path(*---pathway):\n\n");
printf(" ");
for(i=0;i<=maze.r+1;i++)
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++){
printf("%2d",i);
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);
printf("\n\n");
}
}

void main(){
MazeType maze;
PostType start,end;
char cmd;
do{
printf("-------FOUND A MAZEPATH--------\n");
if(!InitMaze(maze)){
printf("\nInitialization errors!!!\n");
exit(OVERFLOW);
}
do{
printf("\nEnter entrance coordinate of the maze: ");
scanf("%d,%d",&start.r,&start.c);
if(start.r>maze.r || start.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(start.r>maze.r || start.c>maze.c);
do{
printf("\nEnter exit coordinate of the maze: ");
scanf("%d,%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))..................................>>>就是在这运行不下去了,请各位大哥大姐看看是那错了,
 printf("\nNo path from entrance to exit!\n");
else
PrintMaze(maze);
printf("\nContinue?(y/n): ");
scanf("%s",&cmd);
}while(cmd=='y' || cmd=='Y');
}


搜索更多相关的解决方案: 算法  

----------------解决方案--------------------------------------------------------

太长了，看不下去……
而且连个注释都没有，题目也该讲讲……


----------------解决方案--------------------------------------------------------

就是用栈写的迷宫，不过大家和他没亲戚关系
所以。。。。。



----------------解决方案--------------------------------------------------------

//base.h
#include <stdio.h> 现在这个可以了,主要是要得出走通迷宫的路径.
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;

//stack.h
#include "base.h"
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{ //迷宫中r行c列的位置
int r;
int c;
}PostType;
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return OK;
}//DestroyStack

//maze.cpp
#include "stack.h"
#define MAXLEN 10//迷宫包括外墙最大行列数目
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#'
}MazeType; //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j;
printf("Enter row and column numbers: ");
scanf("%d%d",&maze.r,&maze.c); //迷宫行和列数
for(i=0;i<=maze.c+1;i++){//迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}//for
for(i=0;i<=maze.r+1;i++){//迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宫
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);//接收障碍的坐标
while(m!=-1){
if(m>maze.r || n>maze.c)//越界
exit(ERROR);
maze.adr[m][n]='#';//迷宫障碍用'#'标记
printf("Enter block's coordinate((-1,-1) to end): ");
scanf("%d%d",&m,&n);
}//while
return OK;
}//InitMaze
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.r][curpos.c]==' ')//可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]='*';//"*"表示可通
return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(ERROR);
}
return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return OK;
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType end){
//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
//并返回TRUE,否则返回FALSE
Stack S;
PostType curpos;
int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e;
InitStack(S);
curpos=start; //设置"当前位置"为"入口位置"
curstep=1; //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,
//即是未曾走到过的通道
FootPrint(maze,curpos);//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e); //加入路径
if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return TRUE; //到达出口
else{
curpos=NextPos(curpos,1);
//下一位置是当前位置的东邻
curstep++; //探索下一步
}//else
}//if
else{ //当前位置不通
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4
&& !StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e);
//留下不能通过的标记,并退一步
}//while
if(e.di < 4){
e.di++;//换下一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是该
//新方向上的相邻
}//if
}//if
}//else
}while(!StackEmpty(S));
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return FALSE;
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
int i,j;
printf("\nShow maze path(*---pathway):\n\n");
printf(" ");
for(i=0;i<=maze.r+1;i++)//打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.r+1;i++){
printf("%2d",i);//打印行名
for(j=0;j<=maze.c+1;j++)
printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记
printf("\n\n");
}
}//PrintMaze

void main(){ //主函数
MazeType maze;
PostType start,end;
char cmd;
do{
printf("-------FOUND A MAZEPATH--------\n");
if(!InitMaze(maze)){ //初始化并创建迷宫
printf("\nInitialization errors!!!\n");
exit(OVERFLOW); //初始化错误
}
do{ //输入迷宫入口坐标
printf("\nEnter entrance coordinate of the maze: ");
scanf("%d%d",&start.r,&start.c);
if(start.r>maze.r || start.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(start.r>maze.r || start.c>maze.c);
do{ //输入迷宫出口坐标
printf("\nEnter exit coordinate of the maze: ");
scanf("%d%d",&end.r,&end.c);
if(end.r>maze.r || end.c>maze.c){
printf("\nBeyond the maze!!!\n");
continue;
}
}while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))//迷宫求解
printf("\nNo path from entrance to exit!\n");
else
PrintMaze(maze);//打印路径
printf("\nContinue?(y/n): ");
scanf("%s",&cmd);
}while(cmd=='y' || cmd=='Y');
}//main


----------------解决方案--------------------------------------------------------
不是亲戚就不能看了吗?这是谁说的,那现在也是这其中的一员,咱们不就是亲戚了吗?要急用,帮忙看看吗?好吗?大哥大姐们
----------------解决方案--------------------------------------------------------

不是那意思~ 我的意思是你什么注释都没有，也不告诉要实现什么

除非是你的亲戚才会看，一楼程序


----------------解决方案--------------------------------------------------------
我把有注释的发上去了,在四楼呢,麻烦楼主帮我看看,急用
----------------解决方案--------------------------------------------------------
以下是引用feng1256在2006-5-14 14:48:00的发言：

就是用栈写的迷宫，不过大家和他没亲戚关系
所以。。。。。


这话我说过
----------------解决方案--------------------------------------------------------

把下面这段看明白你的迷宫就走通了

Stack FoundPath(SqStack S,int maze[N][N])
{
int i=1,j=1,path;

//注意给迷宫出口赋值
maze[N-2][N-2]=88;
while(maze[i][j]!=maze[N-2][N-2])
{
//maze[1][1]为迷宫的入口
if(maze[i][j]==1)
{
path=10*i+j; //把当前可通路径压入栈
S=Push(S,path);
maze[i][j]=0;
j++; //继续向东走
}
else if(maze[i][j]==0) //当前位置不可通，向南走
{
if(!EmptyStack(S)) //当前栈不空
path=*(S.top-1);
i=path/10;
j=path%10;
i++; //向南走
if(maze[i][j]==1)
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向南走不通，向西走
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
j--;
if(maze[i][j]==1) //向西走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else if(maze[i][j]==0) //向西走不通
{
if(!EmptyStack(S))
path=*(S.top-1);
i=path/10;
j=path%10;
i--;
if(maze[i][j]==1) //向北走通
{
path=10*i+j;
S=Push(S,path);
maze[i][j]=0;
j++;
}
else //都走不通时
{
if(!EmptyStack(S))
S=Pop(S,&path);
i=path/10;
j=path%10;
}
}//else
}//else
}//else
}//while
if(maze[i][j]==maze[N-2][N-2])
{
path=10*i+j;
S=Push(S,path);
}

return S;
}


----------------解决方案--------------------------------------------------------
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.