经典迷宫求解问题.c

经典迷宫算法

// 2007-9-13
// 经典迷宫求解问题
// 

#include <stdlib.h>
#include <stdio.h>
#include <string.h> 
#include "com_def.h"
#include "stack.h"


// 地图类型
typedef unsigned short MazeType;

// 墙 Wall
#define W 1
// 空 Space
#define S 0
// 脚印 Foot
#define F 2

// 地图宽度
#define MAPWIDTH   10
// 地图名
#define MAZENAME   maze
// 求地图某点值
#define GETPOS(x,y) ((MazeType)*(MAZENAME+MAPWIDTH*x+y))
#define MAZE(point) GETPOS(point.y,point.x)

// 根据方向下一位置
PosType NextPos(PosType point, int n)
{
    PosType ret = point;
    if(n>4)
        return ret;

    switch(n)
    {
        case 1: ret.x++;break; // right
        case 2: ret.y++;break; // down
        case 3: ret.x--;break; // left
        case 4: ret.y--;break; // up
        default:
            break;
    }
    return ret;
}

bool printpath(ElemType e)
{
    printf("[%d,%d] \n", e.seat.x, e.seat.y);
    return true;
}

// 内存块比较函数
int MEMICMP(void *s1, void *s2, unsigned short n)
{
    unsigned short i = 0;
    while(i<n)
    {
        if (*((char*)s1)++ != *((char*)s2)++)
        {
            return ((char*)s1-(char*)s2)>0?1:-1;
        }
        i++;
    }
    return 0;
}

// 找路算法
bool MazePath(MazeType *maze, PosType start, PosType end)
{
    SqStack  *mstack = NULL;
    ElemType elem;
    PosType curpos;
    bool ret = false;

    // 起点终点判断
    if (MAZE(start)==W || MAZE(end)==W)
        return false;

    mstack = (SqStack*)malloc(sizeof(SqStack));

    // 初始化堆栈
    if (!InitStack(mstack))
        return false;

    // 起点压栈
    elem.ord = 1;
    elem.seat = start;
    elem.di = 1;
    (void)Push(mstack, elem);
    curpos = start;

    do 
    {
        // 当前位置是否可通，是否有足迹
        if (MAZE(curpos) == S)
        {
            // 判断是否终点，是则返回
            if (0==MEMICMP(&curpos, &end, sizeof(curpos)))
            {
                ret = true; 
                break;
            }

            elem.ord = StackLength(mstack);
            elem.di = 1;
            elem.seat = curpos;
            
            // 当前位置压栈
            if (!Push(mstack, elem))
            {
                ret = false; 
                break;
            }

            // 留下足迹
            MAZE(curpos) = F;
            // 当前位置指向当前位置的下一位置（默认方向向右）
            curpos = NextPos(curpos, 1);
        }
        else
        {
            // 当前位置改为栈顶位置的下一位置（按上下左右方向轮流直到结束一个循环）
            // 栈顶的方向跟着变
            if (!GetTop(mstack, &elem))
            {
                ret = false; 
                break;
            }

            if (elem.di < 4)
            {
                elem.di++;
                // 写入栈顶
                Pop(mstack, 0);
                Push(mstack, elem);
                curpos = NextPos(elem.seat, elem.di);
            }
            // 如果栈顶无其他位置可走，则栈顶出栈，继续找
            else
            {
                Pop(mstack, 0);
                GetTop(mstack, &elem);
                curpos = NextPos(elem.seat, elem.di);
            }
        }
    }while(!StackEmpty(mstack));

    // 打印足迹
    if (ret)
    {
        printf("the path is:");
        (void)StackTraverse(mstack, printpath, true);
    }
    else
    {
        printf("there is no path about the maze");
    }

    DestroyStack(mstack);
    return ret;
}

int main()
{
    MazeType maze[10][10] = 
    {
        {W,W,W,W,W,W,W,W,W,W},
        {W,S,S,W,S,S,S,W,S,W},
        {W,S,S,W,S,S,S,W,S,W},
        {W,S,S,S,S,W,W,S,S,W},
        {W,S,W,W,W,S,S,S,S,W},
        {W,S,S,S,W,S,S,S,S,W},
        {W,S,W,S,S,S,W,S,S,W},
        {W,S,W,W,W,S,W,W,S,W},
        {W,W,S,S,S,S,S,S,S,S},
        {W,W,W,W,W,W,W,W,W,W}
    };
    PosType start = {1,1}; 
    PosType end = {8,8};

    MazePath(*maze, start, end);

    return 1;
}