migong.cpp

VC++实现迷宫

// migong.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define  MAXSIZE  20 
#define OK 1
#define ERROR 0   
#define TRUE 1
#define FALSE 0
typedef struct{
	char arr[MAXSIZE][MAXSIZE];
}MazeType; 
typedef struct{
	int r;
	int c;
}PosType;
typedef struct{
	int ord;
	PosType seat;
	int di;
}SELemType;
typedef struct
{
	SELemType stack[MAXSIZE];  
	int  top;          
} sqstack;  
sqstack S;
void InitStack(sqstack &s)
{ 
	s . top = -1;    //设置栈顶指针top，表示栈空
}
int Push(sqstack &s, SELemType x)
{ 
	if (s.top >= MAXSIZE - 1)
		return ERROR;       //栈满，上溢
	else
	{ 
		s.top++;
		s .stack[s.top] = x;
		return OK;
	}
}   //push
int Pop(sqstack &s, SELemType &e)
{ 
	if (s. top < 0)
		return ERROR;       //栈空，下溢
	else 
	{ 
		e = s . stack[s.top];
		s.top--;
		return OK;
	}
}  // pop
int StackEmpty(sqstack s)
{ 
	if (s.top < 0)
		return TRUE;       //栈空，返回TRUE
	else 
	{ 
		return FALSE;
	}
}  // empty

int Pass( MazeType MyMaze,PosType CurPos) 
{
	if (MyMaze.arr[CurPos.r][CurPos.c] == ' ')
		return 1;     // 如果当前位置是可以通过，返回1
	else return 0;  // 其它情况返回0
}

void FootPrint(MazeType &MyMaze,PosType CurPos) 
{
	MyMaze.arr[CurPos.r][CurPos.c] = '*';
}

void MarkPrint(MazeType &MyMaze,PosType CurPos) 
{
	MyMaze.arr[CurPos.r][CurPos.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;
}
int MazePath(MazeType &maze, PosType start, PosType end)// 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE
{ 
	PosType curpos;
	int curstep;
	SELemType e;
	InitStack(S);
	curpos = start;  // 设定"当前位置"为"入口位置"
	curstep = 1;     // 探索第一步
	do {
		if (Pass(maze,curpos))  // 当前位置可通过，即是未曾走到过的通道块
		{ 
			FootPrint(maze,curpos); // 留下足迹
			e.di =1;
			e.ord = curstep;
			e.seat = curpos;
			Push(S,e);              // 加入路径
			if (curpos.r == end.r && curpos.c == end.c)  
				return (TRUE);        // 到达终点（出口）
			curpos = NextPos(curpos, 1);        // 下一位置是当前位置的东邻
			curstep++;                          // 探索下一步
		} 
		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
	} while (!StackEmpty(S) );
	return FALSE;
} // MazePath


int main(int argc, char* argv[])
{
	MazeType maze1;
	PosType start1,end1;
	SELemType e1;
	int l = 0,l1 = 0,r = 0,r1 = 0,n = 0;
	printf("\n请输入迷宫大小:\n");
	printf("行数为line:");
	scanf("%d",&l);
	printf("列数为row:");
	scanf("%d",&r);
	for(int i = 0;i < l;i++)
		for(int j = 0;j < r;j++)
		{
			maze1.arr[i][j] = ' ';
		}
	printf("\n布置迷宫:\n");
	printf("请输入障碍位置:(行(1..line),列(1..row)，输入0,0表示结束)\n");
	scanf("%d,%d",&l1,&r1);
	while(l1 != 0 || r1 != 0)
	{
		if(l1 > l || r1 >r || l1 == 0 || r1 == 0)
		{
			printf("输入错误!请重新输入!\n");
			scanf("%d,%d",&l1,&r1);
		}
		else
			maze1.arr[l1 - 1][r1 - 1] = '$';
		scanf("%d,%d",&l1,&r1);
	}
	printf("\n请输入入口位置:");
	scanf("%d,%d",&l1,&r1);
	start1.r = l1 - 1;
	start1.c = r1 - 1;
	printf("\n请输入出口位置:");
	scanf("%d,%d",&l1,&r1);
	end1.r = l1 - 1;
	end1.c = r1 - 1;
    n = MazePath(maze1,start1,end1);
	if(n)
	{
		printf("\n找到路可走出迷宫!\n");
		printf("按出口到入口顺序打印路径:\n");
		while (!StackEmpty(S))
		{
			Pop(S,e1);
			printf("%d,%d\n",e1.seat.r + 1,e1.seat.c + 1);
		}
	}
	else
		printf("\n未找到路可走出迷宫!\n");
	return 0;
}