甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
1. 题目描述这次的迷宫问题(2)比之前的迷宫问题(1)要复杂了一些，既然是同样问题我们只需要在原来代码的基础上稍加改动即可。
创新互联建站专注于肥城企业网站建设,成都响应式网站建设公司,成都商城网站开发。肥城网站建设公司,为肥城等地区提供建站服务。全流程按需制作，专业设计，全程项目跟踪，创新互联建站专业和态度为您提供的服务
原题链接：地下迷宫_滴滴笔试题_牛客网
题目给定一个N行，M列的数组，以1代表通路，0代表墙体。要求从下标(0,0)的位置走到下标为[0,M-1]的位置，只可以上下左右走，不可斜着走。题目会给定一个体力值，向下走不消耗体力值，向上走消耗3点体力值，向左或者向右走消耗1点体力值，问能否在体力值消耗完之前到达终点，若能输出路径，若不能打印Can Not Escape！。
2. 思路分析整体的代码与迷宫问题(1)相同，但需做出如下改动。
迷宫问题(1)：http://t.csdn.cn/19na2
http://t.csdn.cn/19na2
在输入上多输入一个体力值（Physical Strength Value）即可。
2.2 GetMazePath函数1）：因为该题的最终目的是寻找最短路径，只有这样体力值消耗才最少嘛，所以当找到一条路径后还需要继续找，是否有其他的更短的路径。因此，该函数在找到一条路径后不能结束寻找，而因该回溯到有其他通路的位置，然后继续寻找。所以，该函数不需要返回值。
2）：参数需要增加体力值这个参数，每走一步，对应的参数值都需要做相应的变化。
3）：最短路径的存储：创建一个栈用来存储最短路径，当走到终点时：就需要进行如下判断：在走到终点体力值大于0的前提下，如果存储最短路径的栈为空，或者临时存储路径的栈的大小小于存储最短路径的栈的大小，那么将数据拷贝到最短路径的栈中。否则不拷贝。
4）：这样讲其实不是很清楚，看代码更好理解。被注释的代码就是迷宫(1)中的代码，在迷宫(2)中已经不需要了。
3. 完整代码Stack.h
#include#include
#include#include#include#include#define INIT_STACK_SIZE 4
//数据类型结构体，用来放坐标
typedef struct Position
{
int row;
int col;
}Pos;
typedef Pos ST_DATA_TYPE;
typedef struct Stack
{
ST_DATA_TYPE* data;
int size;
int capacity;
} ST;
void StackInit(ST* st);
void StackDestory(ST* st);
void StackPush(ST* st, ST_DATA_TYPE x);
void StackPop(ST* st);
ST_DATA_TYPE StackTop(ST* st);
int StackSize(ST* st);
bool StackEmpty(ST* st); Stack.c
#include"Stack.h"
void StackInit(ST* st)
{
ST_DATA_TYPE* newlist = (ST_DATA_TYPE*)malloc(sizeof(ST_DATA_TYPE) * INIT_STACK_SIZE);
if (newlist != NULL)
{
st->data = newlist;
st->capacity = INIT_STACK_SIZE;
st->size = 0;
}
}
void StackDestory(ST* st)
{
free(st->data);
st->data = NULL;
}
void StackPush(ST* st, ST_DATA_TYPE x)
{
if (st->size == st->capacity)
{
ST_DATA_TYPE* newlist = (ST_DATA_TYPE*)realloc(st->data, sizeof(ST_DATA_TYPE) * 2 * st->capacity);
if (newlist == NULL)
{
perror("StackPush");
}
else
{
st->data = newlist;
st->capacity *= 2;
}
}
st->data[st->size] = x;
st->size++;
}
void StackPop(ST* st)
{
assert(st->size >0);
st->size--;
}
ST_DATA_TYPE StackTop(ST* st)
{
assert(st);
assert(st->size);
return (st->data[st->size - 1]);
}
int StackSize(ST* st)
{
assert(st->data);
return st->size;
}
bool StackEmpty(ST* st)
{
assert(st->data);
return st->size == 0;
}maze.c
#include"stack.h"
//建立一个全局的栈，用来存储迷宫的路径
ST path;
建立一个栈，用来翻转栈中的数据
ST rpath;
//再建立一个栈判断能走的路径是否是最短的路径
ST MinPath;
//翻转存储迷宫路径的栈，并且打印最终数据
void ShowPath(ST* path, ST* rpath)
{
while (!StackEmpty(path))
{
StackPush(rpath, StackTop(path));
StackPop(path);
}
//while (!StackEmpty(rpath))
//{
// printf("(%d,%d)", StackTop(rpath).row, StackTop(rpath).col);
// printf("\n");
// StackPop(rpath);
//}
//受输出条件变化的影响，输出需做出改变。
//输出栈中元素，只留下一个
while (StackSize(rpath) >1)
{
ST_DATA_TYPE top = StackTop(rpath);
printf("[%d,%d],", top.row, top.col);
//打印一个栈中元素后出栈
StackPop(rpath);
}
}
//判断此路是否能继续往下走
bool IsPath(int** maze, int N, int M, Pos cur)
{
//if (cur.row >= 0
// && cur.row< N
// && cur.col >= 0
// && cur.col< M
// && maze[cur.row][cur.col] == 0)
//
//{
// return true;
//}
//return false;
if (cur.row >= 0
&& cur.row< N
&& cur.col >= 0
&& cur.col< M
&& maze[cur.row][cur.col] == 1)
//将可以走的路换成为1，墙是0
{
return true;
}
return false;
}
//拷贝栈的内容，参数1：被拷贝的栈，参数2：拷贝的目的栈
void StackCopy(ST* ppath, ST* pMinPath)
{
//开辟一个同临时栈的数据容量一样大的空间
pMinPath->data = (ST_DATA_TYPE*)malloc(sizeof(ST_DATA_TYPE) * ppath->capacity);
//将内存拷贝过去
memcpy(pMinPath->data, ppath->data, sizeof(ST_DATA_TYPE) * ppath->size);
//同时赋值给新栈相同的大小和容量
pMinPath->size = ppath->size;
pMinPath->capacity = ppath->capacity;
}
//寻找通路的函数，参数1：迷宫的二维数组，参数2：迷宫的行，参数3：迷宫的列，参数4：存放坐标的结构体
//即使找到了一条通路，那条路也不一定是最终答案，所以不需要通过返回值来结束整个函数
void GetMazePath(int** maze, int N, int M, Pos cur, int PSValue)
{
//入栈，记录路径
StackPush(&path, cur);
//递归的结束条件----到达终点, 修改一下结束条件
if (cur.row == 0 && cur.col == M - 1)
{
//如果说存储最短路径的栈为空或者说新的路径比最短路径还要短，那么拷贝存路径的栈的内容到存最短路径的栈
if (PSValue>= 0 && StackEmpty(&MinPath) || StackSize(&path)< StackSize(&MinPath))
{
//先把原来存最短路径的栈释放掉，防止出现内存泄漏
StackDestory(&MinPath);
StackCopy(&path, &MinPath);
}
}
//定义结构体，表示下一个要走的位置
Pos next;
//进这个函数就表示此位置已经走过，改变该坐标的值，防止出现死递归
maze[cur.row][cur.col] = 2;
//定义一个结构体用来表示下一个将要走的坐标
//向上走，列不变行减一
next = cur;
next.row -= 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
GetMazePath(maze, N, M, next, PSValue - 3);
}
//向下走，列不变行加一
next = cur;
next.row += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
GetMazePath(maze, N, M, next, PSValue);
}
//向左走，行不变列减一
next = cur;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
GetMazePath(maze, N, M, next, PSValue - 1);
}
//向右走，行不变列加一
next = cur;
next.col += 1;
//判断该点是否能走
if (IsPath(maze, N, M, next))
{
GetMazePath(maze, N, M, next, PSValue - 1);
}
//回退的同时需要将原来走过的路恢复成1
maze[cur.row][cur.col] = 1;
//走到这里代表此坐标上下左右都走不通，开始回退
StackPop(&path);
}
int main()
{
//迷宫的初始化，N行M列的数组
int N, M;
scanf("%d %d", &N, &M);
//输入体力值physical strength value
int PSValue;
scanf("%d", &PSValue);
//动态开辟二维数组
//二维数组的行指针
int** maze = (int**)malloc(sizeof(int*) * N);
//二维数组的列指针
int i = 0;
for (i = 0; i< N; i++)
{
maze[i] = (int*)malloc(sizeof(int) * M);
}
int k, m;
for (k = 0; k< N; k++)
{
for (m = 0; m< M; m++)
{
scanf("%d", &maze[k][m]);
}
}
//入口的坐标
Pos cur = { 0,0 };
//初始化栈
StackInit(&path);
StackInit(&MinPath);
StackInit(&rpath);
//寻找通路的函数
GetMazePath(maze, N, M, cur, PSValue);
if (StackEmpty(&MinPath))
{
printf("Can not escape!");
}
else
{
//打印数据
ShowPath(&MinPath, &rpath);
}
//释放空间
//释放每一行的空间
for (i = 0; i< N; i++)
{
free(maze[i]);
}
//释放列的指针
free(maze);
maze = NULL;
//销毁栈
StackDestory(&path);
StackDestory(&MinPath);
StackDestory(&rpath);
return 0;
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧