题解 | #地下迷宫#

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
#include<math.h>
#include<ctype.h>
#include<assert.h>
#include<stdbool.h>
#include<errno.h>
#include<malloc.h>
#include<stddef.h>
typedef struct Position
{
  int row;
  int col;
}PT;
typedef PT STDataType;
typedef struct stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int SizeStack(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)

{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;//这是指向栈顶数据的下一个
	//ps->top=-1  这是指向栈定数据
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newCapacity=ps->capacity == 0 ?  4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;//创造的空间要给ps->a
		ps->capacity = newCapacity;
	}

	
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
int SizeStack(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}
ST path;
ST minpath;
//输出栈里面的坐标路径
void PrintPath(ST* ps)
{
    //path数据倒到rpath;
    ST rpath;
    StackInit(&rpath);
    while(!StackEmpty(ps))//不用改变值所以不用传地址
    {
        StackPush(&rpath,StackTop(ps));
        StackPop(ps);
    }
    while(SizeStack(&rpath)>1)
    {
        PT top=StackTop(&rpath);
        printf("[%d,%d],",top.row,top.col);
        StackPop(&rpath);
    }
     PT top=StackTop(&rpath);
        printf("[%d,%d]",top.row,top.col);
        StackPop(&rpath);
        StackDestroy(&rpath);
}

bool Ispass(int n,int m,int maze[n][m],PT pos)
{
        if(pos.row>=0&&pos.row<n&&pos.col>=0&&pos.col<m
           &&maze[pos.row][pos.col]==1)
           {
            return true;
           }
           else {
           return false;
           }
}
 void StackCopy(ST* path,ST* pcopy)
 {
     pcopy->a=(STDataType*)malloc(sizeof(STDataType)*path->capacity);
     memcpy(pcopy->a,path->a,sizeof(STDataType)*path->top);
     pcopy->capacity=path->capacity;
     pcopy->top=path->top;
 }
void GetMazePath(int n,int m,int maze[n][m],PT cur,int P)
{
    StackPush(&path,cur);//把找到的路径入栈
    //如果走到出口
     if(cur.row==0&&cur.col==m-1)
     {
        //找到更短路径,更新minpath
        if(P>=0&&StackEmpty(&minpath)
            || SizeStack(&path)<SizeStack(&minpath))
            {
                StackDestroy(&minpath);//先销毁minpath的空间，避免空间泄露
                StackCopy(&path,&minpath);//把最短入境拷贝成minpath
            }
            
     }
     //探测上下左右4个位置
     PT next;
     maze[cur.row][cur.col]=2;//把找对的位置设置成2
     //上
     next=cur;
     next.row-=1;
     if(Ispass(n,m,maze,next))
     {
        GetMazePath(n,m,maze,next,P-3);
     }
     //下
     next=cur;
     next.row+=1;
      if(Ispass(n,m,maze,next))
     {
        GetMazePath(n,m,maze,next,P);
     }
     //左
     next=cur;
     next.col-=1;
     if(Ispass(n,m,maze,next))
     {
        GetMazePath(n,m,maze,next,P-1);
     }
     //右
     next=cur;
     next.col+=1;
     if(Ispass(n,m,maze,next))
     {
        GetMazePath(n,m,maze,next,P-1);
     }
     //恢复在来，因为要找最短路径
     maze[cur.row][cur.col]=1;
     StackPop(&path);//把入栈的数删除了  循环会反复调用所有可以删除掉所有







}
int main() {
    int n=0,m=0,P=0;
    while(scanf("%d %d %d",&n,&m,&P)!=EOF)
    {
         int maze[n][m];//输入
         for(int i=0;i<n;i++)
         {
            for(int j=0;j<m;j++)
            {
                scanf("%d ",&maze[i][j]);
            }
         }
         //先初始化栈
         StackInit(&path);
         StackInit(&minpath);
         PT entry={0,0};
         GetMazePath(n,m,maze,entry,P);
         if(!StackEmpty(&minpath))
         {
            PrintPath(&minpath);
         }
         else 
         {
             printf("Can not escape!");
         }
         StackDestroy(&path);
         StackDestroy(&minpath);
        
             


    }
    return 0;
}