程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> 二維數組-這是一個迷宮求解問題

二維數組-這是一個迷宮求解問題

編輯：編程解疑
這是一個迷宮求解問題

/*如果迷宮有通道可解則正常運行，迷宮不可解為什麼顯示exe停止工作呢？怎樣修改呢？*/
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define COLUMN 10
#define ROW 10

typedef int Status;

typedef struct{
char **maze;
int **footprint;
int row;
int column;
}MazeType;

typedef struct{
int x;
int y;
}PosType;

typedef struct{
int ord;
PosType seat;
int di;
}SElemType;

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

Status InitStack(SqStack *S);

Status InitMaze(MazeType *M);

Status DestroyStack(SqStack *S);

Status ClearStack(SqStack *S);

Status StackEmpty(SqStack S);

int StackLength(SqStack S);

Status GetTop(SqStack S,SElemType *e);

Status Push(SqStack *S,SElemType e);

Status Pop(SqStack *S,SElemType *e);

Status StackTraverse(const SqStack *S);

Status PrintMaze(MazeType *M);

Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end);

Status FootPrint(MazeType *M,PosType pos);

Status Pass(MazeType *M,PosType pos);

SElemType NewSElem(int step,PosType pos,int d);

PosType NextPos(PosType pos,int d);

Status MarkPrint(MazeType *M,PosType pos);

Status PrintFoot(MazeType *M,SqStack *S);

int main()
{
MazeType maze;
SqStack stack;
PosType start,end;
start.x=0;start.y=1;
end.x=8;end.y=9;
InitMaze(&maze);
printf("迷宮形狀：\n");
PrintMaze(&maze);
if(TRUE==MazePath(&stack,maze,start,end))
printf("迷宮可解.\n");
else
printf("迷宮不可解.\n");
return 0;
}

Status InitStack(SqStack *S){
//構造一個空棧S
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)//分配失敗
{
printf("分配內存失敗.\n");
exit(0);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}

Status InitMaze(MazeType M){
//初始化迷宮數據
int i,j;
char mz[ROW][COLUMN]={ //mz新定義的二維數組
'#',' ',' ','#','#','#','#','#','#','#',//每行十個
'#','#','#','#',' ',' ',' ','#',' ','#',
'#',' ',' ','#',' ',' ',' ','#',' ','#',
'#',' ',' ',' ',' ','#','#',' ',' ','#',
'#',' ','#','#','#',' ',' ',' ',' ','#',
'#',' ',' ',' ','#',' ','#',' ','#','#',
'#',' ','#',' ',' ',' ','#',' ',' ','#',
'#',' ','#','#','#',' ','#','#',' ','#',
'#','#',' ',' ',' ',' ',' ',' ',' ',' ',
'#','#','#','#','#','#','#','#','#','#'
};
M->maze=(char *)malloc(sizeof(char )*ROW);
M->footprint=(int *)malloc(sizeof(int *)*ROW);
if(!M->maze||!M->footprint){
printf("申請空間失敗，迷宮無法初始化.\n");
return ERROR;
exit(0);
}
for(i=0;i M->maze[i]=(char *)malloc(sizeof(char)*COLUMN);
M->footprint[i]=(int *)malloc(sizeof(int)*COLUMN);
if(!M->maze[i]||!M->footprint[i]){
printf("申請空間失敗，迷宮初始化失敗.\n");
return ERROR;
exit(0);
}
}
for(i=0;i for(j=0;j M->maze[i][j]=mz[i][j];
M->footprint[i][j]=0;
}
}
M->row=ROW;
M->column=COLUMN;
return OK;
}

Status DestroyStack(SqStack *S){

if(!S)
{
    printf("指針為空，釋放失敗.\n");
    exit(0);
}
free(S);
return OK;

}

Status ClearStack(SqStack *S){

if(!S)
    return FALSE;
S->top=S->base;
return OK;

}

Status StackEmpty(SqStack S){

if(S.top==S.base)
    return TRUE;
else
    return FALSE;

}

int StackLength(SqStack S){

return S.stacksize;

}

Status GetTop(SqStack S,SElemType *e){

if(S.top==S.base){
    printf("棧為空.\n");
    return FALSE;
}else{
    *e=*(S.top-1);
    printf("棧頂元素：%c\n",*e);
    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)
    {
        printf("重新申請空間失敗.\n");
        exit(0);
    }
    S->top=S->base+S->stacksize;
    S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;

}

Status Pop(SqStack *S,SElemType *e){

if(S->top==S->base){//棧為空
    printf("棧為空.\n");
    return ERROR;
}
*e=*(--S->top);
return OK;

}

Status StackTraverse(const SqStack *S){
//從棧底到棧頂依次對每個元素進行訪問
SElemType *p=S->base;
if(S->base==S->top)
{
printf("棧為空.\n");
return FALSE;
}
printf("棧中元素：");
while(p!=S->top)
{
printf("x=%d,y=%d\n",p->seat.x,p->seat.y);
*p++;
}
printf("\n");
return OK;
}

Status PrintMaze(MazeType *M){
//輸出迷宮
int i,j;
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
printf("%c",M->maze[i][j]);
}
printf("\n");
}
printf("\n");
return OK;
}

Status PrintFoot(MazeType *M,SqStack *S){
//輸出迷宮的路徑
int i,j;
SElemType *p;
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
M->footprint[i][j]=0;
}
}
p=S->base;
if(S->base==S->top)
{
printf("棧為空.\n");
return FALSE;
}
while(p!=S->top)
{
M->footprint[p->seat.x][p->seat.y]=1;
*p++;
}
for(i=0;irow;i++){
for(j=0;jcolumn;j++){
printf("%d",M->footprint[i][j]);
}
printf("\n");
}

return OK;

}

Status MazePath(SqStack *S,MazeType maze,PosType start,PosType end){

int curstep=1;//當前步數
SElemType e;
PosType curpos=start;//當前位置
InitStack(S);//初始化棧
do{
    if(TRUE==Pass(&maze,curpos)){
        FootPrint(&maze,curpos);
        e=NewSElem(curstep,curpos,1);
        Push(S,e);
        if((curpos.x==end.x)&&(curpos.y==end.y)){//到達終點（出口）
            printf("迷宮路徑:\n");
            //StackTraverse(S);
            PrintFoot(&maze,S);
            return TRUE;
        }
        curpos=NextPos(curpos,1);
        curstep++;
    }//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
//PrintFoot(&maze,S);
}while(!StackEmpty(*S));//一直循環到棧空為止
return FALSE;

}

Status FootPrint(MazeType *M,PosType pos){
//將迷宮的當前位置pos設置為"走過"，即footprint該位置為1
if((pos.x>M->row)||(pos.y>M->column))//檢驗大小
return FALSE;
M->footprint[pos.x][pos.y]=1;//如果不滿足條件,開始運行下一步
return TRUE;
}

Status Pass(MazeType *M,PosType pos){
//判斷當前位置是否可通，即為走過的通道塊
if((M->rowcolumn printf("位置越位.\n");
exit(0);
}
if((0==M->footprint[pos.x][pos.y])&&(M->maze[pos.x][pos.y]==' '))
return TRUE;
else
return FALSE;
}

SElemType NewSElem(int step,PosType pos,int d){
//創建新結點，用step，pos，d初始化該結點
SElemType e;
e.ord=step;
e.seat=pos;
e.di=d;
return e;//下一步
}

PosType NextPos(PosType pos,int d){
//獲取pos位置d方向的位置
switch(d){
case 1://東
pos.x++;
break;
case 2://南
pos.y++;
break;
case 3://西
pos.x--;
break;
case 4://北
pos.y--;
break;
default:
printf("位置編號出錯.\n");
}//利用坐標左西右東上北下南
return pos;
}

Status MarkPrint(MazeType *M,PosType pos){
//將迷宮M的pos位置，設為已走，成功返回OK；否則返回ERROR
if(pos.x>M->row||pos.y>M->column){
printf("所要標記位置越位.\n");
return ERROR;
}
M->footprint[pos.x][pos.y]=1;
return OK;
}

最佳回答：


http://blog.csdn.net/zhuxiangfeicool/article/details/6916827

  1. 上一頁:
  2. 下一頁:
編程解疑
安卓 html5-APP如何嵌入h5或JSP等頁面

APP如何嵌入h5或JSP等
datagridview-C#控件DataGridView中的columns該怎麼用呢，求大神幫我解決一下這個問題

C#控件DataGridVi
關於java問題-幫我看下eclipse怎麼回事

幫我看下eclipse怎麼回
java源碼-求助Java這個題目，求源碼⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

求助Java這個題目，求源碼
c++入門-codewars 小白傷心 大神來掃一眼

codewars 小白傷心

javascript-JS如何獲取某個div下存在多少個子div

JS如何獲取某個div下存在
相關文章
閱讀排行榜
imageview-布局中使用ImageView OOM（急） mfc-MFC的記事本文件打開的問題，續 棋盤-一道編程題，不懂，求教 java集合問題-集合中關於addAll的一些問題 stream-java8有關steam的問題？ 32位-vs2010中使用#define _USE_32BIT_TIME_T無效 xml-oracle數據庫 mybatis 插入方法 操作系統-誰能簡要講解一下UNIX和windows中創建新進程的方式 vb-VB一個關於字符串生成的問題 javascript-JS中如何從數組中獲取自己想要的值？ word-Inglish-Number Translator
熱門圖文
整理php防注入和XSS攻擊通用過濾，phpxss ECSHOP：首頁實現顯示子分類商品，並實現點擊Tab頁切換分類商品 PHP函數超時處理方法 C++之基於排序方法求一組數的中位數，一組中位數 php5魔術函數、魔術常量 動態創建Repeater，綁定數據 完美的2個php檢測字符串是否是utf-8編碼函數分享 多線程同步問題
欄目導航
匯編語言DelphiGroovyWebSphereRationalPythonRuby編程解疑編程綜合問答更多關於編程編程問題解答
Copyright © 程式師世界 All Rights Reserved