【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。
【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。
找到一条从起点到终点的迷宫路径，并将路径输出。如果从起点到终点没有路径，则输出NO PASS!注：所有迷宫的起点为左上角，终点为右下角。【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。
【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。
【样例输入】
0111111
0011101
1001101
0011001
1000111
1110000
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
//创建一个点的数据类型
typedef struct Coordinate
{
int row;
int col;
}Coor;
/
typedef Coor STD;
typedef struct Stack
{
STD* base;
int top;
int capacity;
}S;
void StackInit(S* ps)
{
assert(ps);
ps->base = (STD*)malloc(sizeof(STD) * 4);
if (ps->base == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
void StackDestory(S* ps)
{
assert(ps);
free(ps->base);
ps->base = NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(S* ps, STD x)
{
assert(ps);
// 满了-》增容
if (ps->top == ps->capacity)
{
STD* tmp = (STD*)realloc(ps->base, ps->capacity * 2 * sizeof(STD));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->base = tmp;
ps->capacity *= 2;
}
}
ps->base[ps->top] = x;
ps->top++;
}
// 出栈
void StackPop(S* ps)
{
assert(ps);
// 栈空了，调用Pop，直接中止程序报错
assert(ps->top > 0);
//ps->a[ps->top - 1] = 0;
ps->top--;
}
STD StackTop(S* ps)
{
assert(ps);
// 栈空了，调用Top，直接中止程序报错
assert(ps->top > 0);
return ps->base[ps->top - 1];
}
int StackSize(S* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(S* ps)
{
assert(ps);
return ps->top == 0;
}
/
//栈的文件
S Path;
bool checkCoor(int**maze, int N, int M, Coor coor)
{
if ((coor.row >= 0 && coor.col < N)
&& (coor.row >= 0 && coor.col < M)
&& maze[coor.row][coor.col] == 0)
return true;
else
return false;
}
bool SearchmazePath(int**maze, int N, int M, Coor coor)
{
//点入栈
StackPush(&Path, coor);
if (coor.row == N - 1 && coor.col == M - 1)//找到目标位置返回真
return true;
Coor next;
maze[coor.row][coor.col] = 2;//将走过的点标记为2
//分别对上、下、左、右四个方向进行判断，递归调用。
next = coor;
next.col += 1;
if (checkCoor(maze, N, M, next))
{
if (SearchmazePath(maze, N, M, next))
return true;
}
next = coor;
next.col -= 1;
if (checkCoor(maze, N, M, next))
{
if (SearchmazePath(maze, N, M, next))
return true;
}
next = coor;
next.row -= 1;
if (checkCoor(maze, N, M, next))
{
if (SearchmazePath(maze, N, M, next))
return true;
}
next = coor;
next.row += 1;
if (checkCoor(maze, N, M, next))
{
if (SearchmazePath(maze, N, M, next))
return true;
}
//为到达目标点，弹出数据，递归回退。
StackPop(&Path);
return false;
}
void PrintPath(S*path)
{
S rpath;//在创建一个栈
StackInit(&rpath);
while (!StackEmpty(path))//将原栈的数据存入逆序栈中
{
StackPush(&rpath, StackTop(path));
StackPop(path);
}
while (!StackEmpty(&rpath))
{
Coor c = StackTop(&rpath);
printf("(%d,%d)\n", c.row, c.col);//进行打印
StackPop(&rpath);
}
StackDestory(&rpath);
}
int main()
{
int N, M;
while (scanf("%d%d", &N, &M)!=EOF)
{
int**maze = (int**)malloc(sizeof(int*)*N);
for (int i = 0; i < N; i++)
maze[i] = (int*)malloc(sizeof(int)*M);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
scanf("%d", &maze[i][j]);
}
StackInit(&Path);
Coor start = { 0,0 };
if (SearchmazePath(maze, N, M, start))
{
//printf("找到出口了,路径如下:\n");
PrintPath(&Path);
}
else
printf("NO PASS!\n");*/
StackDestory(&Path);
for (int i = 0; i < N; i++)
free(maze[i]);
free(maze);
maze = NULL;
}
return 0;
}