迷宫求解出问题，帮看看。

返回值总是不通。
帮忙看看谢谢！

#include<stdlib.h>
#include<malloc.h>
#include<stdio.h>
#define stack_size 100
#define increase 50
#define TRUE 1
#define FALSE 0


int mazemap[10][10]=
{
        {0,0,0,0,0,0,0,0,0,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,1,1,0,0,1,1,0},   
        {0,1,0,0,0,1,1,1,1,0},   
        {0,1,1,1,0,1,1,1,1,0},   
        {0,1,0,1,1,1,0,1,1,0},   
        {0,1,0,0,0,1,0,0,1,0},   
        {0,1,1,1,1,1,1,1,1,0},   
        {0,0,0,0,0,0,0,0,0,0},   
};

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

typedef struct
{
    int di;   
    pos seat; 
    int ord;
}maze;

typedef struct
{
    maze *base;
    maze *top;  
    int stacksize;      
}pmaze; 

pmaze s;

int init(pmaze *p)  
{
    p->base=(maze *)malloc(stack_size*sizeof(maze));
    if(p->base==NULL)
    {
        exit(0);
    }
    p->stacksize=stack_size;
    p->top=p->base;
    return(TRUE);
}

int pass(pos e)
{
    if(mazemap[e.x][e.y]==0||mazemap[e.x][e.y]==3)
    {
        return(FALSE);
    }
    return(TRUE);
}

int push(pmaze *p,maze e)
{
    if(p->top-p->base>=p->stacksize)
    {
        p->base=(maze *)realloc(p->base,(stack_size+increase)*sizeof(maze));
        if(p->base==NULL)
        {
            exit(0);
        }
        p->stacksize+=increase;
    }

    *p->top++=e;
    return(TRUE);
}

int pop(pmaze *p,maze *e)   
{
    if(p->top==p->base)
    {
        return(FALSE);
    }
    *e=*--p->top;  
    return(TRUE);
}

int stackempty(pmaze *p)
{
    if(p->top==p->base)
    {
        return(TRUE);
    }
    return(FALSE);
}

void nextpos(maze *e,pos e1)
{
    switch(e->di)
    {
        case 1:e1.y++;break;
        case 2:e1.x++;break;
        case 3:e1.y--;break;
        case 4:e1.x--;break;
    }
}

void footprint(pos *e)
{
    mazemap[e->x][e->y]=3;
}


int mazepath(pos start,pos end,int (*mazemap)[10])
{
    maze e;
    pos xy;
    int   curstep=1;   
    init(&s);
    xy=start;
    do
    {
        if(pass(xy))
        {
            e.di=1;
            e.seat=xy;
            e.ord=curstep;
            footprint(&xy);
            push(&s,e);
            if(xy.x==end.x&&xy.y==end.y)
            {
                return(TRUE);
            }
            nextpos(&e,xy);
            curstep++;
        }
            else
            {
                if(!stackempty(&s))
                {
                    pop(&s,&e);
                }
                if(e.di==4&&!stackempty(&s))
                {
                    mazemap[e.seat.x][e.seat.y]=3;
                    pop(&s,&e);
                }
                if(e.di<4)
                {
                    e.di++;
                    push(&s,e);
                    nextpos(&e,e.seat);
                    curstep=e.ord+1; 
                    xy=e.seat;
                }
            }
    }while(!stackempty(&s));
    return(FALSE);
}


int main(void)
{
    int   t,i,j;     
    pos   start={1,1},end={8,8};   
    t=mazepath(start,end,mazemap);   
    mazepath(pos start,pos end,int (*mazemap)[6])
    printf("%d",t);
    getchar();  
}

6 个解决方案

#1

这里有返回值的函数都是返回TRUE或者FALSE，有什么看不懂的？
难道TRUE是什么意思不懂？

#2

#include<stdlib.h>
#include<malloc.h>
#include<stdio.h>
#define stack_size 100
#define increase 50
#define TRUE 1
#define FALSE 0

int mazemap[10][10]=
{
        {0,0,0,0,0,0,0,0,0,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,1,1,0,0,1,1,0},   
        {0,1,0,0,0,1,1,1,1,0},   
        {0,1,1,1,0,1,1,1,1,0},   
        {0,1,0,1,1,1,0,1,1,0},   
        {0,1,0,0,0,1,0,0,1,0},   
        {0,1,1,1,1,1,1,1,1,0},   
        {0,0,0,0,0,0,0,0,0,0},   
};

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

typedef struct
{
    int di;   
    pos seat; 
    int ord;
}maze;

typedef struct
{
    maze *base;
    maze *top;  
    int stacksize;      
}pmaze; 

pmaze s;

int init(pmaze *p)  
{
    p->base=(maze *)malloc(stack_size*sizeof(maze));
    if(p->base==NULL)
    {
        exit(0);
    }
    p->stacksize=stack_size;
    p->top=p->base;
    return(TRUE);
}

int pass(pos e)
{
    if(mazemap[e.x][e.y]==0 || mazemap[e.x][e.y]==3)
    {
        return(FALSE);
    }
    return(TRUE);
}

int push(pmaze *p,maze e)
{
    if(p->top - p->base >= p->stacksize)
    {
        p->base = (maze *)realloc(p->base,(p->stacksize+increase)*sizeof(maze));
        if(p->base==NULL)
        {
            exit(0);
        }
p->top = p->stacksize+p->base;
        p->stacksize += increase;
    }
    *p->top++ = e;
    return(TRUE);
}

int pop(pmaze *p,maze *e)   
{
    if(p->top==p->base)
    {
        return(FALSE);
    }
    *e=*--p->top;  
    return(TRUE);
}

int stackempty(pmaze *p)
{
    if(p->top == p->base)
    {
        return(TRUE);
    }
    return(FALSE);
}

void nextpos(maze *e,pos e1)
{
    switch(e->di)
    {
        case 1:e1.y++;break;
        case 2:e1.x++;break;
        case 3:e1.y--;break;
        case 4:e1.x--;break;
    }
}

void footprint(pos *e)
{
    mazemap[e->x][e->y]=3;
}

int mazepath(pos start, pos end, int (*mazemap)[10])
{
    maze e;
    pos xy;
    int  curstep=1;   
    init(&s);
    xy = start;
    do
    {
        if (pass(xy))
        {
            e.di=1;
            e.seat=xy;     //当前坐标
            e.ord=curstep;
            footprint(&xy);//留下足迹
            push(&s,e);
            if(xy.x == end.x && xy.y == end.y)//是否到达出口
            {
                return(TRUE);
            }
            nextpos(&e,xy);
            curstep++;
        }
        else
        {
            if(!stackempty(&s))
            {
                    pop(&s,&e);                
                while (e.di==4 && !stackempty(&s))
                {
                    mazemap[e.seat.x][e.seat.y]=0;
                    pop(&s,&e);
                }
                if(e.di<4)
                {
                    e.di++;
                    push(&s,e);
                    nextpos(&e,e.seat);
                    curstep=e.ord+1; 
                    xy=e.seat;
                }
}
}
    }while(!stackempty(&s));
    return(FALSE);//这里执行完之后,返回值肯定为FALSE嘛.
}

int main(void)
{
    int  t;     
    pos  start={1,1},end={8,8};   
    t = mazepath(start,end,mazemap);   
    printf("%d\n",t);//所以输出结果为0
    return 0;
}

#3

不妨参考一下这个程序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define Stacksize 100
#define StackIncrement 10
typedef struct
{
int ord; //通道块在路径上的序号
int x,y; //通道块在迷宫中的位置
int di;  //从此通道块走向下一通道块的方向
}SElemType;//栈的元素类型

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

void push(SqStack &S, SElemType e)
{
if (S.top - S.base >= Stacksize)
{
S.base = (SElemType *)realloc(S.base,(S.stacksize+StackIncrement)*sizeof(SElemType));
if (!S.base)
{
exit(0);
}
S.top = S.base+Stacksize;
        S.stacksize += StackIncrement;
}
*S.top++ = e;
}

void pop(SqStack &S, SElemType &e)
{
if (S.base == S.top)
{
exit(0);
}
e = *--S.top;
}

void InitStack(SqStack &S)
{
S.base = (SElemType *)malloc(sizeof(SElemType) * Stacksize);
if (!S.base)
{
exit(0);
}
S.top = S.base;
S.stacksize = Stacksize;
}

void NextPos(int &x, int &y, int direction)
{
switch(direction)
{
   case 1:x++;break;  //东
   case 2:y++;break;  //南
   case 3:x--;break;  //西
   case 4:y--;break;  //北
   default:exit(0);
}
}

int main(void)
{
SqStack S;
    SElemType e;
int i=0,j=0;
int x=1,y=0;  //初始位置
int curstep = 1; //搜索第一步
    char maze[10][10]={
{'#',' ','#','#','#','#','#','#','#','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ',' ',' ','#','#',' ',' ','#'},
{'#',' ','#','#','#',' ',' ',' ',' ','#'},
{'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
{'#',' ','#',' ',' ',' ','#',' ',' ','#'},
{'#',' ','#','#','#','#','#','#',' ','#'},
{'#','#',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#',' ','#'},
};
InitStack(S);
for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
printf("%c ",maze[i][j]);
}
printf("\n");
}
printf("\n");
do
{
if (maze[y][x] == ' ')    //当前位置可以通过,即是未曾走到过的通道块
{
            maze[y][x] = '1';   //留下足迹
e.x = x;
e.y = y;
e.ord = curstep;
e.di = 1;    //首次往东走
push(S, e);
if (x==8 && y==9) //到达出口
{
break;
}
NextPos(x, y, 1); //首次往东走
curstep++;   //走向下一步
}
else   //当前位置不可以通过
{
if (S.base != S.top) 
{
pop(S, e);
while (e.di == 4 && S.base != S.top) //留下不能通过的标志，并后退一步
{
maze[e.y][e.x] = '0';
pop(S, e);
}
if (e.di < 4)  //换个方向走
{
e.di++;
push(S, e);
NextPos(e.x, e.y, e.di);
x = e.x;  //设定新的坐标为当前位置
y = e.y;
}
}
}
}while (S.base != S.top);
    for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
printf("%c ",maze[i][j]);
}
printf("\n");
}
free(S.base);
S.base = S.top;
return 0;
}

#4

大哥们，谢谢你们的回复。
我的意思你们理解错了，发贴那阵急着去上自习，把表达内容没写明白。

不是看不懂，我想说的是地图起点到终点是通路，但是却返回FALSE(表示不通)。
我不知道错在哪里了，麻烦给看看。

#5

论坛帖子不能编辑，第一次没描述清楚，麻烦给看看程序哪里有问题。

地图是通路但却返回不通。

#6

那就是你写的函数有问题呗。
刚写好的：

#include <stdio.h>

#define WALL '0'
#define WAY  '1'
#define PATH '2'
#define DEAD '3'

#define WALL_SYMBOL '='
#define WAY_SYMBOL  ' '
#define PATH_SYMBOL '.'
#define DEAD_SYMBOL 'x'
#define TMP_SYMBOL  'x'

typedef enum tagBOOL {
	false = 0,
	true  = 1,
} bool;

typedef enum direction {
	EAST  = 0,
	SOUTH = 1,
	WEST  = 2,
	NORTH = 3,
} DIRECTION;

typedef struct position {
	int x;
	int y;
} POSITION, *PPOSITION;

typedef struct step {
	int i;
	POSITION where;
	DIRECTION d;
} STEP, *PSTEP;

char MAZE[11][11] = {
	"0000000000",
	"0110111010",
	"0110111010",
	"0111100110",
	"0100011110",
	"0111011110",
	"0101110110",
	"0100010010",
	"0011111110",
	"0000000000",
	{ 0 },
};

POSITION ENTER = {
	.x = 1,
	.y = 1,
};

POSITION EXIT = {
	.x = 8,
	.y = 8,
};

STEP path[128] = { { 0 }, };
PSTEP bottom = path, top = path;

void printMAZE();
bool MazePath();
bool isDead(PPOSITION where);
bool isEnd(PPOSITION current, PPOSITION end);
bool isEmpty(PSTEP bottom, PSTEP top);
void MarkPath(PPOSITION where);
void MarkDead(PPOSITION where);
void StepOne(PPOSITION current, PPOSITION old, DIRECTION d);
void push(PSTEP *top, PSTEP step);
void pop(PSTEP *top, PSTEP step);

int main()
{
	printMAZE();
	if(MazePath())
		printf("There is a solution:\n");
	else
		printf("There is no solution!\n");
	printMAZE();

	return 0;
}

void printMAZE()
{
	for(int i = 0; i < 10; ++i)
	{
		for(int j = 0; j < 10; ++j)
		{
			switch(MAZE[i][j]) {
			case WALL:
				putchar(WALL_SYMBOL);
				break;
			case WAY:
				putchar(WAY_SYMBOL);
				break;
			case PATH:
				putchar(PATH_SYMBOL);
				break;
			case DEAD:
				putchar(DEAD_SYMBOL);
				break;
			default:
				putchar(MAZE[i][j]);
			}
		}
		putchar('\n');
	}
}

bool MazePath()
{
	POSITION current = ENTER;
	int n = 0;
	bool bReturn = false;

	do {
		if(!isDead(&current))
		{
			MarkPath(&current);
			STEP step = { n, current, EAST };
			push(&top, &step);
			if(isEnd(&current, &EXIT))
			{
				bReturn = true;
				break;
			}
			StepOne(&current, &current, EAST);
			n++;
		}
		else
		{
			if(!isEmpty(bottom, top))
			{
				STEP step;
				pop(&top, &step);
				while(step.d == NORTH && !isEmpty(bottom, top))
				{
					MarkDead(&step.where);
					pop(&top, &step);
				}
				if(step.d < NORTH)
				{
					step.d++;
					push(&top, &step);
					StepOne(&current, &step.where, step.d);
				}
			}
		}
	} while(!isEmpty(bottom, top));

#if 0
	if(bReturn)
	{
		PSTEP tmp = bottom;
		while(tmp != top)
		{
			MAZE[tmp->where.x][tmp->where.y] = 'a' + tmp->i;
			tmp++;
		}
	}
#endif

	return bReturn;
}

bool isDead(PPOSITION where)
{
	return (
		MAZE[where->x][where->y] == WALL ||
		MAZE[where->x][where->y] == PATH ||
		MAZE[where->x][where->y] == DEAD);
}

bool isEnd(PPOSITION current, PPOSITION end)
{
	return (current->x == end->x && current->y == end->y);
}

bool isEmpty(PSTEP bottom, PSTEP top)
{
	return bottom == top;
}

void MarkPath(PPOSITION where)
{
	MAZE[where->x][where->y] = PATH;
}

void MarkDead(PPOSITION where)
{
	MAZE[where->x][where->y] = DEAD;
}

void StepOne(PPOSITION current, PPOSITION old, DIRECTION d)
{
	current->x = old->x;
	current->y = old->y;
	switch(d) {
	case EAST:
		current->y++;
		break;
	case SOUTH:
		current->x++;
		break;
	case WEST:
		current->y--;
		break;
	case NORTH:
		current->x--;
		break;
	}
}

void push(PSTEP *top, PSTEP step)
{
	(*top)->i = step->i;
	(*top)->where = step->where;
	(*top)->d = step->d;
	(*top)++;
}

void pop(PSTEP *top, PSTEP step)
{
	(*top)--;
	step->i = (*top)->i;
	step->where = (*top)->where;
	step->d = (*top)->d;
}

/////////////////////////////////////////
=  =   = =
=    ==  =
= ===    =
=   =    =
= =   =  =
= === == =
==       =
==========
There is a solution:
==========
=..=xxx= =
= .=xxx= =
=..xx==  =
=.===    =
=...=    =
= =...=  =
= ===.== =
==   ....=
==========