标题:求解答,迷宫求解
只看楼主
wangcwei
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:10
专家分:23
注 册:2017-11-27
 问题点数:0 回复次数:2 
求解答,迷宫求解
迷宫求解,运行后程序不输出修改后的地图,具体也不知道程序具体错在哪里

#include "stdafx.h"#include "stdlib.h"
#define STACK_INIT_SIZE  100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACKIN 10
typedef int Status;
typedef int 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;

SqStack S;
Status InitStack(SqStack &S) {
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S.base)exit(EOVERFLOW);
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
};//构造空栈
Status DestroyStack(SqStack &S) {
    free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.stacksize = 0;
    return 0;
};//销毁栈
int StackLength(SqStack S) {
    return S.top - S.base;
};//返回栈的长度
Status StackEmpty(SqStack S) {
    if (S.base == S.top)
        return TRUE;
    else
        return FALSE;
};//若栈S为空,返回TRUE,否则返回FALSE
Status StackFull(SqStack S) {
    if (S.top - S.base >= S.stacksize)
        return TRUE;
    else
        return FALSE;
};//若栈S为满,返回TRUE,否则返回FALSE
Status GetTop(SqStack S, SElemType &e) {
    if (S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
};//若栈不空,用e返回返回S的栈顶元素,并返回OK,否则返回ERROR
Status Pop(SqStack &S, SElemType &e) {
    if (!StackEmpty(S))return FALSE; //判断栈是否为空
    e = *--S.top;
    S.top--;
    return OK;
};//若栈不空,用e返回栈顶的值返回TRUE否则返回FALSE
Status Push(SqStack &S, SElemType e) {
    if (StackFull(S))
    {
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKIN) * sizeof(SElemType));
        if (!S.base)exit(EOVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKIN;
    }
    *S.top++ = e;
    return OK;
};//插入e为栈顶元素
int Pass(PosType coordinate, MazeType passmaze[10][10]) {
    if (passmaze[coordinate.x][coordinate.y] == 1)
        return OK;
    else
        return FALSE;
};//判断当前位置是否可通过
void FootPrint(PosType coordinate, MazeType footmaze[10][10]) {
    footmaze[coordinate.x][coordinate.y] = 2;
};//留下足迹
int comper(PosType a1, PosType a2) {
    if (a1.x == a2.x && a1.y == a2.y)
    {
        return TRUE;
    }
    else
        return FALSE;
};//PosType结构体之间的比较函数
PosType NextPos(PosType coordinate, Status x) {
    switch (x)
    {
    case 1:
        coordinate.y += 1;
        break;
    case 2:
        coordinate.x += 1;
        break;
    case 3:
        coordinate.x -= 1;
        break;
    case 4:
        coordinate.y -= 1;
        break;
    }
    return coordinate;
};
void MarkPrint(PosType coordinate, MazeType markmaze[10][10]) {
    markmaze[coordinate.x][coordinate.y] = 3;
};
Status MaxePath(MazeType maze[10][10], PosType start, PosType end) {
    PosType curpos;
    InitStack(S);
    int curstep = 1;
    SElemType e;
    curpos = start;
    do
    {
        if (Pass(curpos, maze)) {
            FootPrint(curpos, maze);
            e.ord = curstep;
            e.seat = curpos;
            e.di = 1;
            Push(S, e);
            if (comper(curpos, end)) return TRUE;
            curpos = NextPos(curpos, 1);
            curstep++;
        }
        else {
            if (!StackEmpty(S))
            {
                Pop(S, e);
                while (e.di == 4 && !StackEmpty(S))
                {
                    MarkPrint(curpos, maze);
                    Pop(S, e);
                }
                if (e.di < 4) {
                    e.di++;
                    Push(S, e);
                    curpos = NextPos(e.seat, e.di);
                }
            }
        }
    } while (!StackEmpty(S));
    return FALSE;
};
void printfmaze(MazeType maze[10][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++)
        {
            printf("%d ", maze[i][j]);
        }
        printf("\r\n");
    }
}//输出地图
int main()
{
    PosType start, end;
    MazeType maze[10][10] = {
        { 0,0,0,0,0,0,0,0,0,0 },
        { 0,1,0,0,0,1,1,0,0,0 },
        { 0,1,1,1,1,1,0,0,0,0 },
        { 0,0,0,1,0,0,0,0,0,0 },
        { 0,0,0,1,0,0,0,0,0,0 },
        { 0,0,1,1,0,0,0,0,0,0 },
        { 0,0,0,1,1,1,1,1,0,0 },
        { 0,0,0,0,0,0,0,1,0,0 },
        { 0,0,0,0,0,0,0,1,1,0 },
        { 0,0,0,0,0,0,0,0,0,0 },
    };
    start.x = 1; start.y = 1;
    end.x = 8; end.y = 8;
    printfmaze(maze);
    if (MaxePath(maze, start, end) )
    {
        printfmaze(maze);
    }
    else
    {
        printf("迷宫不可解");
    }
    scanf_s("");
    return 0;
}



搜索更多相关主题的帖子: int base top return 返回 
2017-11-27 14:07
wangcwei
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:10
专家分:23
注 册:2017-11-27
得分:0 
求帮助啊大佬们
2017-11-27 14:18
wangcwei
Rank: 2
来 自:河北
等 级:论坛游民
帖 子:10
专家分:23
注 册:2017-11-27
得分:0 
已经自己解决了。发现两处问题
程序代码:
Status Pop(SqStack &S, SElemType &e) {
    if (StackEmpty(S))return FALSE; //判空函数返回值逻辑错误了
    e = *--S.top;
    //S.top--;             //这一行应当去除
    return OK;
};
第二处在函数中MaxePath
程序代码:
 while (e.di == 4 && !StackEmpty(S))
     {
        MarkPrint(e.seat, maze);//这里传递的第一个实参传错参数
        Pop(S, e);
     }
2017-11-28 20:12



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-482867-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.122685 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved