思路

本题与（DD3 地下迷宫）相似，在地下迷宫的基础上增加了体力值的限制。

当一个矩阵被确定时，青蛙移动的水平位移已经被确定为矩阵的长度，即青蛙水平移动消耗的体力已经被确定了。所以我们只需要考虑上下方向的移动：上下移动的位移越小，则消耗的体力值越少，所以青蛙的体力消耗主要取决于上下位移。同时上下位移越小，青蛙的移动路径越短，所以问题就转化成了：求青蛙离开的最短路径。

与DD3 地下迷宫不同的是，本题找到一条可行路径时不直接一路返回，而是回到关键位置继续搜索其他路径，所以这里的搜索函数不再设置返回值。需要注意的是，返回时要将路径中的位置重新置为 1，以便后续搜索。在搜索期间，若可行路径比minPath短且体力值不小于0，则替换minPath。最终若minPath不为空则进行打印，否则无法逃出迷宫。

代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

//**----------------------------------------------------
#define INIT_SIZE 10
#define EXP_SIZE 10

typedef int* STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}ST;

void StackInit(ST* st);
void StackPush(ST* st, const STDataType x);
void StackPop(ST* st);
void StackDestory(ST* st);
STDataType StackTopData(const ST* st);
bool StackEmpty(const ST* st);

void StackInit(ST* st)
{
	st->data = (STDataType*)malloc(INIT_SIZE * sizeof(STDataType));
	if (st->data == NULL)
	{
		perror("StackInit:");
		return;
	}
	st->capacity = INIT_SIZE;
	st->top = 0;
}

void StackPush(ST* st, const STDataType x)
{
	assert(st);
	if (st->top == st->capacity)
	{
		//expand
		STDataType* tmp = (STDataType*)realloc(st->data, sizeof(STDataType) * (st->top + EXP_SIZE));
		if (tmp != NULL)
		{
			st->data = tmp;
            st->capacity += EXP_SIZE;
		}
		else
		{
			perror("Expand:");
			return;
		}
	}
	st->data[st->top] = x;
	st->top++;
}

void StackPop(ST* st)
{
	assert(st);
	assert(st->top > 0);
	st->top--;
}

void StackDestory(ST* st)
{
	free(st->data);
	st->data = NULL;
}

STDataType StackTopData(const ST* st)
{
	assert(st);
	assert(st->top > 0);//不允许栈为空
	return st->data[st->top - 1];
}

bool StackEmpty(const ST* st)
{
	assert(st);
	return st->top == 0;
}

int StackSize(const ST* st)
{
	return st->top;
}
//**----------------------------------------------------
//以上为栈的接口实现

ST path;//记录路径
ST minPath;//记录最短路径

//打印最短路径
void PrintStack(ST* ps)
{
	ST rPath;
	StackInit(&rPath);
	while (!StackEmpty(ps))
	{
		StackPush(&rPath, StackTopData(ps));
		StackPop(ps);
	}
    StackDestory(ps);
	while (StackSize(&rPath) > 1)
	{
		int* tmp = StackTopData(&rPath);
		printf("[%d,%d],", tmp[0], tmp[1]);
		StackPop(&rPath);
	}
    int* tmp = StackTopData(&rPath);
    printf("[%d,%d]", tmp[0], tmp[1]);
    StackPop(&rPath);

    StackDestory(&rPath);
}

//深拷贝栈
void StackCopy(ST* sTDest, ST* sTSour)
{
    StackDestory(sTDest);
    StackInit(sTDest);
    sTDest->data = (STDataType*)malloc(sizeof(STDataType) * StackSize(sTSour));
    memcpy(sTDest->data, sTSour->data, sizeof(STDataType) * StackSize(sTSour));
    sTDest->top = sTSour->top;
    sTDest->capacity = sTSour->capacity;
}

//DFS寻找最短路径
void FindPath(int** maze, int row, int col, int x, int y, int p)
{
	int* Pos = (int*)malloc(sizeof(int) * 2);
	Pos[0] = x;
	Pos[1] = y;
	StackPush(&path, Pos);

	if (x < 0 || x >= row || y < 0 || y >= col || maze[x][y] != 1)
	{
		StackPop(&path);
		return;
	}

	if ((x == 0) && (y == col - 1))
	{
		if (p >= 0 && (StackEmpty(&minPath) || StackSize(&path) < StackSize(&minPath)))
		{
			StackCopy(&minPath, &path);
		}
	}

	maze[x][y] = 2;

	FindPath(maze, row, col, x - 1, y, p - 3);
    FindPath(maze, row, col, x + 1, y, p);
    FindPath(maze, row, col, x, y - 1, p - 1);
    FindPath(maze, row, col, x, y + 1, p - 1);

    maze[x][y] = 1;
	StackPop(&path);
}

int main()
{
	int row = 0;
	int col = 0;
    int p = 0;
	scanf("%d %d %d", &row, &col, &p);

	int** maze = (int**)malloc(sizeof(int*) * row);
	for (int i = 0; i < row; i++)
	{
		maze[i] = (int*)malloc(sizeof(int) * col);
	}

	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			scanf("%d", &maze[i][j]);
		}
	}

	StackInit(&path);
    StackInit(&minPath);

	FindPath(maze, row, col, 0, 0, p);

    if(!StackEmpty(&minPath))
    {
    	PrintStack(&minPath);
    }
    else
    {
        printf("Can not escape!\n");
    }

	for (int i = 0; i < row; i++)
	{
		free(maze[i]);
		maze[i] = NULL;
	}
	maze = NULL;
	return 0;
}