【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。

Question

【问题描述】下图给出了一个迷宫的平面图，其中标记为黑色的为障碍，标记为白色的为可以通行的区域。迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。

找到一条从起点到终点的迷宫路径，并将路径输出。如果从起点到终点没有路径，则输出NO PASS!注：所有迷宫的起点为左上角，终点为右下角。【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。
【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。
【样例输入】
0111111
0011101
1001101
0011001
1000111
1110000

Answer 1

#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;
}