PTA|7-2 迷宫 (30分)【数据结构】

用一个m×n的二维数组表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，按顺时针方向求出一条从人口到出口的通路，或得出没有通路的结论。

输入格式:
输入的第一行中给出m和n的整数值 ，分别代表迷宫的行数和列数。m和n的值，均小于20。 接着是两行分别是迷宫的入口和出口位置
然后是m×n的二维数组表示迷宫

输出格式:
输出是m×n的二维数组，表示迷宫每一步走的位置，使用%3d格式。

输入样例1:

9 8
1 1
9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0

输出样例1:

  1  2  0  0  0  0  0  0
  0  3  0  0  0  0  0  0
  5  4  0  0  0  0  0  0
  6  0  0  0  0  0  0  0
  7  8  9  0 13 14 15  0
  0  0 10 11 12  0 16  0
  0  0  0  0  0  0 17  0
  0  0  0  0  0  0 18  0
  0  0  0  0  0  0 19 20

输入样例2:

6 5
1 1
6 5
0 0 0 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0

输出样例2:

NO

思路
第一眼看到这题时，感觉有点无从下手，但仔细分析，你会发现并不难，只是需要清晰的循环思路
（我在分析思路时喜欢拿张纸一步步写出来，这题的思路图会在下面贴出）
这题我定义了两个二维数组：1）Maze储存迷宫 2）ord储存路径
一个栈：S
Maze就一个用处——看当前的点可不可通（是不是墙or是否走过），当前元素不等于0的，一律会被Pass函数判断为不可通
ord的作用也很简单，就为了输出路径（有它完全是因为题目输出格式的需要）
最关键的还是S，S负责储存路径，在走错时出栈
储存在栈S内的每个元素都是一个结构体
结构体里有三个元素，分别是：
ord：储存第几步
seat：当前步数对应的坐标
di：走向下一个坐标的方向（东–0；南–1；西–2；北–3）

（要是还是看不进去，不懂的，就看代码注释，我都很详细的介绍了用途）

完整代码
<全局定义部分>

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE   100    //存储空间初始分配
#define STACKINCREMENT  10       //存储空间分配增量
#define TRUE 1
#define FALSE 0
#define  OK  1
#define  ERROR  -1
#define  OVERFLOW -2
#define  MAX 25    //题目中说m、n不超过20
int curstep=2;     //与MazePath函数中的不同，这是一个全局常量，功能不是记录步数，而是相当于“打墙”
typedef int MazeType[MAX][MAX];  //定以MazeType[][]类型
MazeType Maze;     //全局变量迷宫，这样就不用在函数中频繁引用
typedef int Status;

//定义结构体 
typedef struct
{  int x,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(OVERFLOW);            //存储分配失败
    s.top=s.base;
    s.stacksize = STACK_INIT_SIZE;
    return OK;
}

Status GetTop(SqStack s, SElemType &e)
{ //获取栈顶元素 
    if(s.top==s.base) return ERROR;
    e=*(s.top-1);
    return OK;
}

Status Push(SqStack &s,SElemType e)
{//插入元素e为新的栈顶元素
    if(s.top-s.base>=STACK_INIT_SIZE){//栈满,追加存储空间
        s.base = (SElemType*)realloc(s.base, (s.stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!s.base)exit(OVERFLOW);           //存储分配失败
        s.top = s.base + s.stacksize;
        s.stacksize +=STACKINCREMENT;
    }
    *s.top++=e;
    return OK;
}

Status Pop(SqStack &s,SElemType &e)  
{ //出栈顶元素
    if(s.base==s.top) return ERROR;
    e=*--s.top;
    return OK;
}

<与迷宫有关的函数部分>

void creatMaze(int m,int n)
{//创建迷宫，并在外围加墙 
	int i,j; 
	for(i=1;i<m+1;i++)
		for(j=1;j<n+1;j++)
			scanf("%d",&Maze[i][j]);
	//打墙 
    for(i=0;i<n+2;i++){	Maze[0][i]=1; Maze[m+1][i]=1;}
	for(i=1;i<m+1;i++){	Maze[i][0]=1; Maze[i][n+1]=1;}
}

Status FootPrint(PosType curpos)
{//记录位置curpos已经搜索过 
	Maze[curpos.x][curpos.y]=curstep;
} 

Status Pass(PosType curpos)
{//返回位置curpos是否可通（搜索过） 
	if(Maze[curpos.x][curpos.y]==0){return OK;	}
	else{return 0;	}
}

PosType NextPos(PosType curpos,int i)
{//返回从位置curpos按方向i到达的新位置 
	switch(i){
		case 0:
			curpos.y+=1;
			break;
		case 1:
			curpos.x+=1;
			break;
		case 2:
			curpos.y-=1;
			break;
		case 3:
			curpos.x-=1;
			break;
	}
	return curpos;
}

Status MarkPrint(PosType curpos)
{//记录位置curpos4个方向都搜索过不可通 
	Maze[curpos.x][curpos.y]=1;
	return 1;
}


Status MazePath(PosType start,PosType end)
{//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中
 //（从栈底到栈顶），并返回TRUE；否则返回FALSE
 InitStack(S);                   //建栈  
 SElemType e;
 PosType curpos=start;           //设定“当前位置”为“入口位置”
 int curstep=1;                  //第一步
 do 
 {
 	if(Pass(curpos)){            //当前位置可以通过，即未曾走到过的通道块 
 		FootPrint(curpos);       //留下足迹 
		e.ord=curstep;
		e.seat.x=curpos.x; e.seat.y=curpos.y;
		e.di=0;
		Push(S,e);               //加入路径           
		if(curpos.x==end.x&&curpos.y==end.y) return(TRUE);  //到达终点（出口） 
		curpos=NextPos(curpos,e.di );      //否则走向下一位置，当前位置的东邻 
		curstep++;               //探索下一步 
	}else{                       //当前位置不能通过，序号不为0 
	 	if(S.base!=S.top){      //判断栈是否为空 
	 		Pop(S,e); curstep--; //不空就退回上一步 
	 		while(e.di==4&&!StackEmpty(S))  //一直后退直到找到能走的路径 
			 {MarkPrint(e.seat); Pop(S,e);} //留下不能通过的标记，并退回一步 
			if(e.di<4){
				e.di++; Push(S,e); curstep++;//换下一个方向探索 
				curpos= NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻块        
			} 
		}
	} 
  }while(S.base!=S.top);
  return(FALSE); 
}

<主函数部分>

int main()
{
	int flag=1;
	SElemType e;
    int m,n,i,j;
    scanf("%d%d",&m,&n);
    int ord[m+2][n+2]={0};//Maze数组存迷宫、ord数组存路径次序（初始化元素全为0） 
	PosType start,end;  //输入入口出口 
	scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
	creatMaze(m,n);  //建立迷宫 
    if(MazePath(start,end)==FALSE){printf("NO"); flag=0;}//用MazePath函数寻找路径，找不到打印NO（start的di>4时） 
    else{  //找到了，讲栈内元素导入ord二维数组 
    	while(S.base!=S.top){ //当栈不空时 
    		Pop(S,e) ;
    		ord[e.seat.x][e.seat.y]=e.ord;
		} 
	}
	//最后打印ord数组
	if(flag==1)
	for(i=1;i<m+1;i++){
		for(j=1;j<n+1;j++)
			printf("%3d",ord[i][j]);
		printf("\n");
	}
		
    return 0;
}

运行结果