用棧實現的自動走迷宮

[cpp
sqStack.h 
#include "selemtype.h" 
#define MaxSize 1000 
typedef struct 
{ 
    SElemType data[MaxSize]; 
    int top; 
}Stack; 
 
Status InitStack(Stack &S); 
Status DestroyStack(Stack &S); 
Status StackEmpty(Stack &S); 
Status Push(Stack &S,SElemType &e); 
Status Pop(Stack &S,SElemType &e); 
[cpp] view plaincopy
sqStack.cpp 
 
#include "sqstack.h" 
#include<iostream> 
using namespace std; 
Status InitStack(Stack &S) 
{    
    S.top = 0 ; 
    for( int i = 0 ; i < MaxSize ; i++ ) 
    { 
        S.data[i].di = 0 ; 
        S.data[i].ord = 0 ;  
        S.data[i].seat.c = 0; 
        S.data[i].seat.r = 0; 
    } 
    return true; 
} 
Status DestroyStack(Stack &S) 
{ 
    S.top = 0 ; 
    return true; 
} 
Status StackEmpty(Stack &S) 
{ 
    bool judger = false ; 
    if(S.top == 0) 
        judger = true; 
    return judger; 
} 
Status Push(Stack &S,SElemType &e)  
{ 
    bool judger = false; 
    if(S.top < MaxSize) 
    { 
         
        S.data[S.top] = e ; 
        S.top++; 
        judger = true ; 
    } 
    return judger; 
} 
Status Pop(Stack &S,SElemType &e) 
{    
    bool judger = false ; 
    if(S.top > 0) 
    { 
        S.top--; 
        e = S.data[S.top] ; 
        judger = true ;  
         
    } 
    return judger; 
} 
[cpp] 
Mazepath.h 
 
#define N 15 
#define M 22 
//分割塊占總空間比例 
#define V 0.4 
typedef struct ElemType 
{ 
    int x,y; 
    char c; 
}ElemType; 
typedef struct MazeType 
{ 
    ElemType arr[N][M];  
}MazeType; 
 
Status Pass(MazeType &MyMaze, PosType CurPos); 
void FootPrint(MazeType &MyMaze, PosType CurPos); 
void MarkPrint(MazeType &MyMaze, PosType CurPos); 
PosType NextPos(PosType CurPos, int Dir); 
Status MazePath(MazeType &maze, PosType start, PosType end); 
[cpp] 
Mazepath.cpp 
 
/*------------------------------------------------
    走迷宮算法v1.0
N            迷宮行數
M            迷宮列數
V            分割塊占總空間比例
ElemType     迷宮元素類型
MazeType     迷宮類型
 
函數MazePath   走迷宮算法
函數Pass       判斷當前位置是否可通過
函數FootPrint  留下足跡
函數MarkPrint  留下不能再走的標記
函數NextPos    計算下一位置
-------------------------------------------------*/ 
#include "MazePath.h" 
Status MazePath(MazeType &maze, PosType start, PosType End) 
{ 
    // 算法3.3 
    // 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中 
    // （從棧底到棧頂），並返回TRUE；否則返回FALSE    
    Stack stack;   //定義一個棧 
    InitStack(stack);  //初始化該棧 
    int count = 0 ;   //用來記錄通道塊的序號 
    PosType nextPos = start,curPos = start; 
    SElemType e,pe; 
    pe.di = 0; 
    int di = 0 ; 
    bool judger = true ; 
    bool uu = true; 
    while(true) 
    { 
         
        for(int i = 1 ; i <= 4 ; i++ ) 
        { 
                nextPos = NextPos(curPos,i); 
                if(Pass(maze,nextPos)) 
                { 
 
                    count++; 
                    e.seat = curPos ; 
                    e.ord = count; 
                    e.di = i ; 
                    FootPrint(maze,curPos); 
                    Push(stack, e); 
                    curPos = nextPos ; 
                    judger = true ; 
                    if(curPos.c==End.c&&curPos.r==End.r) 
                    { 
                        count++; 
                        e.seat = curPos ; 
                        e.ord = count; 
                        e.di = i ; 
                        FootPrint(maze,curPos); 
                        Push(stack, e); 
                        return true ; 
                    } 
                    break; 
                } 
            if(i == 4) 
            { 
                if(judger)  //走投無路時將最後一個通道塊壓入棧 
                { 
 
                    count++; 
                    e.seat = curPos ; 
                    e.ord = count; 
                    e.di = i ; 
                    FootPrint(maze,curPos); 
                    Push(stack, e);  
                    judger = false; 
                    if(curPos.c==End.c&&curPos.r==End.r) 
                        return true ; 
                } 
                Pop(stack , pe);   //出棧 
                curPos = pe.seat ; 
                MarkPrint(maze , pe.seat);    //標記為走過且不可走 
                if(stack.top == 0) 
                    return false; 
                break; 
            } 
             
        } 
    } 
 
 
}  //MazePath 
 
Status Pass( MazeType &MyMaze,PosType CurPos)  
{ 
    if (MyMaze.arr[CurPos.r][CurPos.c].c==' ') 
        return 1;     // 如果當前位置是可以通過，返回1 
    else return 0;  // 其它情況返回0 
} 
 
void FootPrint(MazeType &MyMaze,PosType CurPos)  
{ 
    //循環是判斷全局線程互斥變量的值，等待走步， 
    //值為false，迷宮走步，並重新設為true，交給 
    //主線程繪制，子線程等待 
    while(drawflag) 
        ; 
    drawflag=true; 
    MyMaze.arr[CurPos.r][CurPos.c].c='*'; 
     
} 
 
void MarkPrint(MazeType &MyMaze,PosType CurPos)  
{ 
    //循環是判斷全局線程互斥變量的值，等待走步， 
    //值為false，迷宮走步，並重新設為true，交給 
    //主線程繪制，子線程等待 
    while(drawflag) 
        ; 
    drawflag=true; 
    MyMaze.arr[CurPos.r][CurPos.c].c='!'; 
} 
 
PosType NextPos(PosType CurPos, int Dir)  
{ 
    PosType ReturnPos;  
    switch (Dir)  
    { 
    case 1: 
        ReturnPos.r=CurPos.r; 
        ReturnPos.c=CurPos.c+1; 
        break; 
    case 2: 
        ReturnPos.r=CurPos.r+1; 
        ReturnPos.c=CurPos.c; 
        break; 
    case 3: 
        ReturnPos.r=CurPos.r; 
        ReturnPos.c=CurPos.c-1; 
        break; 
    case 4: 
        ReturnPos.r=CurPos.r-1; 
        ReturnPos.c=CurPos.c; 
        break; 
    } 
    return ReturnPos; 
} 
[cpp] view plaincopy
selemtype.h 
 
#pragma once 
#define Status bool 
#define TRUE true 
#define FALSE false 
struct PosType  
{ 
    int r,c;             //行列 or xy 
}; 
 
typedef struct 
{ 
    int ord;            //通道塊在路徑上的序號 
    PosType seat;       //通道塊在迷宮中的坐標位置 
    int di;             //從此通道塊走向下一通道塊的方向 
}SElemType; 
extern bool drawflag;   //全局變量外部聲明 
[cpp] 
main.cpp 
 
#include <iostream> 
using namespace std; 
#include "graphics.h" 
#include <time.h> 
#include "mazepath.h" 
/*------------------------------------------------
    走迷宮游戲v1.0
屏幕大小：   640*480
Width        每個小方塊寬度
Space        每個小方塊間隔
Step         每塊占據象素
 
drawflag     線程互斥全局變量，為true畫圖，
             為false走迷宮
threadflag   判斷線程是否結束的全局變量，為false
             線程結束，程序結束
maze;        迷宮全局對象
start,end    迷宮起終點全局變量
 
 
函數InitMaze        初始化迷宮
函數RandmMaze       隨機生成迷宮
函數DrawMaze        繪制迷宮
函數ThreadMazePath  子線程函數，調用走迷宮函數修
                    改迷宮對象數據
    算法設計思想
數據結構：     迷宮每個元素由位置坐標x,y和是否可走
               的狀態c構成，x、y代表畫塊的左上角坐
               標，c為#是障礙，為空格是空位，為！
               是已走過且不能再走，為*是走過且還有
               選擇；
基本操作：     棧的初始化、銷毀、入棧、出棧等;
繪制迷宮操作： 在主線程中繪制，根據元素值c選擇不同
               顏色繪制，根據元素值x、y，確定繪制
               位置；
走迷宮操作：   在子線程中計算迷宮對象走動的每一步，
               修改迷宮對象的值，但不繪制迷宮，通
               過修改互斥變量drawflag的值，在兩個
               線程中交替進行繪制和走步。                
-------------------------------------------------*/ 
#define Width 24 
#define Space 2 
#define Step  (Width + Space) 
 
bool drawflag=true; 
MazeType maze; 
PosType start,End; 
bool threadflag=true; 
 
void InitMaze(MazeType &maze) 
{ 
    //初始化迷宮,將二維數組的每個元素計算出屏幕坐標 
    int i,j; 
    for(i=0;i<N;i++) 
        for(j=0;j<M;j++) 
        { 
            maze.arr[i][j].x=30+j*Step; 
            maze.arr[i][j].y=30+i*Step; 
        } 
} 
void RandmMaze(MazeType &maze,PosType start,PosType end) 
{ 
    //隨機生成迷宮，在二維數組內除起終點外其余位置隨 
    //機生成障礙，障礙數量按比例V計算 
    int i,j,k,num; 
    //邊界和空位初始化 
    for(i=0;i<N;i++) 
    { 
        maze.arr[i][0].c='#'; 
        maze.arr[i][M-1].c='#';      
 
        if(i!=0&&i!=N-1) 
        { 
            for(j=1;j<M-1;j++) 
            { 
                maze.arr[i][j].c=' '; 
            } 
        } 
    } 
    for(i=1;i<M-1;i++) 
    { 
        maze.arr[0][i].c='#'; 
        maze.arr[N-1][i].c='#'; 
    } 
 
    //按分割塊占總空間比例隨機生成迷宮 
    num=(N-2)*(M-2)*V;   //計算需要的分割塊數量 
 
    maze.arr[start.r][start.c].c='#'; //為了隨機生成分割塊不占用起始和終止位置 
    maze.arr[end.r][end.c].c='#'; 
 
    k=num;  
    while(k>1) 
    { 
        i=rand()%(N-2)+1;j=rand()%(M-2)+1; 
        if(maze.arr[i][j].c==' ') 
            maze.arr[i][j].c='#'; 
        k--; 
    } 
    maze.arr[start.r][start.c].c=' '; 
    maze.arr[end.r][end.c].c=' ';    
 
} 
void DrawMaze(MazeType &maze) 
{ 
    //繪制迷宮，按不同狀態繪制不同顏色方塊 
    int i,j; 
         
    for(i=0;i<N;i++) 
    { 
        for(j=0;j<M;j++) 
        { 
            switch(maze.arr[i][j].c) 
            { 
            case '#':   //障礙塊 
                setfillstyle(SOLID_FILL,LIGHTBLUE); 
                break; 
            case '!':   //已走過且無路可走的塊 
                setfillstyle(SOLID_FILL,LIGHTRED); 
                break; 
            case '*':   //走過的塊 
                setfillstyle(SOLID_FILL,LIGHTGREEN); 
                break; 
            case ' ':   //空閒塊 
                setfillstyle(SOLID_FILL,BLACK); 
                break; 
            } 
            bar(maze.arr[i][j].x,maze.arr[i][j].y,maze.arr[i][j].x+Width,maze.arr[i][j].y+Width); 
        } 
        //cout<<endl; 
    } 
 
} 
 
DWORD WINAPI ThreadMazePath(LPVOID plParameter) 
{ 
    //子線程函數，調用走迷宮函數修改迷宮對象數據 
    //迷宮無解再生成新迷宮，直到有解 
    int k=1; 
    srand(time(0)); 
    RandmMaze(maze,start,End); //隨機生成迷宮 
 
    while(!MazePath(maze,start,End)) 
    {        
        cout<<"第"<<k<<"個迷宮無解！"<<endl; 
         
        getchar(); 
        InitMaze(maze); 
        RandmMaze(maze,start,End);k++;       
    } 
    cout<<"第"<<k<<"個迷宮有解！"<<endl; 
     
    setfillstyle(SOLID_FILL,BLACK); 
    bar(100,450,500,480); 
    setcolor(YELLOW); 
    SetFont(16,16,0,0,0,FALSE,FALSE,FALSE,"宋體"); //文字設為宋體 
    outtextxy(100,450,"此迷宮有通路!"); 
 
    threadflag=false;  //線程結束標記 
    return 0; 
} 
void main() 
{ 
    //初始化圖形界面 
    initgraph(640,480); 
    //清屏 
    cleardevice(); 
 
    //默認全局變量為true 
    drawflag=true;    
    threadflag=true; 
 
     
    InitMaze(maze);     //初始化迷宮對象 
     
    start.r=start.c=1;  //初始化起終點 
    End.r=N-2;End.c=M-2; 
 
    //創建走迷宮數據計算子線程 
    HANDLE hThread1=CreateThread(NULL, 
        0,ThreadMazePath,NULL,0,NULL); 
 
    while(threadflag)   //子線程未結束 
    { 
        Sleep(100); 
        if(drawflag)     //線程互斥變量為真，畫圖，否則等待迷宮走完一步 
        { 
            DrawMaze(maze);  
            drawflag=false;  //畫完一步，置為假，迷宮數據計算子線程走下一步 
        } 
    } 
 
    //結束前任意鍵暫停 
    getchar(); 
    //關閉圖形界面 
    closegraph(); 
 
}