#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct Postion
{
int row;
int col;
}PT;
///////////////////////////////////////////////////////////////////////
typedef PT STDataType;
typedef struct StackNode
{
STDataType* a;
int capacity;
int top;
}SN;
//初始化
void Stackinit(SN* pq)
{
assert(pq);
pq->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (pq->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
pq->capacity = 4;
pq->top = 0;
}
}
//清空
void StackDestroy(SN* pq)
{
assert(pq);
free(pq->a);
pq->a = NULL;
pq->top = pq->capacity = 0;
}
//入栈
void StackPush(SN* pq, STDataType x)
{
assert(pq);
if (pq->top == pq->capacity)
{
STDataType*tmp = (STDataType*)realloc(pq->a, sizeof(STDataType) * 2 * pq->capacity);
if (pq->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
pq->capacity *= 2;
pq->a = tmp;
}
}
pq->a[pq->top] = x;
pq->top++;
}
//出栈
void StackPop(SN* pq)
{
assert(pq);
assert(pq->top > 0);
pq->top--;
}
//打印栈顶
STDataType Stacktop(SN* pq)
{
assert(pq);
assert(pq->top > 0);
return pq->a[pq->top - 1];
}
//元素个数
int Stacksize(SN* pq)
{
assert(pq);
return pq->top;
}
//判断是否为空
int StackEmpty(SN* pq)
{
assert(pq);
if (pq->top == 0)
{
return 1;
}
else
{
return 0;
}
}
//栈的全局变量
SN path;
SN minpath;
///////////////////////////////////////////////////////////////////////
//打印
void PrintMaze(SN* minpath)
{
SN ps;
Stackinit(&ps);
while(!StackEmpty(minpath))
{
StackPush(&ps,Stacktop(minpath));
StackPop(minpath);
}
while(Stacksize(&ps)>1)//打印路径，最后一个不要 逗号，
{
PT top=Stacktop(&ps);
printf("[%d,%d],",top.row,top.col);
StackPop(&ps);
}
//打印路径的最后一个
PT top=Stacktop(&ps);
printf("[%d,%d]",top.row,top.col);
StackPop(&ps);
StackDestroy(&ps);
}
//判断是否越界或者是墙壁或者走过的路
int IsPass(int** maze,int M,int N,PT pos)
{
if(pos.row>=0 && pos.row<M
&& pos.col>=0 && pos.col<N
&& maze[pos.row][pos.col]==1)
{
return 1;
}
else
{
return 0;
}
}
//将path中的数据拷贝到minpath
void StackCopy(SN* ppath,SN* pcopy)
{
pcopy->a=(STDataType*)malloc(sizeof(STDataType*)* ppath->capacity);
if(pcopy->a==NULL)
{
printf("pcopy->a malloc fail\n");
}
else
{
memcpy(pcopy->a,ppath->a,sizeof(STDataType)* ppath->top);
pcopy->top=ppath->top;
pcopy->capacity=ppath->capacity;
}
}
//栈的全局变量的初始化
void GetMazePath(int** maze,int M,int N,PT cur,int P)
{
StackPush(&path,cur); //把坐标记录进栈
//出口
if(cur.row==0 && cur.col==N-1)
{
if(P>=0 && StackEmpty(&minpath)
|| Stacksize(&path)<Stacksize(&minpath))
{
StackDestroy(&minpath); //清除minpath的空间
StackCopy(&path,&minpath); //将path中的数据拷贝到minpath
}
}
PT next;
maze[cur.row][cur.col]=2; //走过的路标记为2
//上
next=cur;
next.row -=1;
if(IsPass(maze,M,N,next)) //判断是否越界或者是墙壁
{
GetMazePath(maze,M,N,next,P-3);
}
//下
next=cur;
next.row +=1;
if(IsPass(maze,M,N,next)) //判断是否越界或者是墙壁
{
GetMazePath(maze,M,N,next,P);
}
//左
next=cur;
next.col -=1;
if(IsPass(maze,M,N,next)) //判断是否越界或者是墙壁
{
GetMazePath(maze,M,N,next,P-1);
}
//右
next=cur;
next.col +=1;
if(IsPass(maze,M,N,next)) //判断是否越界或者是墙壁
{
GetMazePath(maze,M,N,next,P-1);
}
maze[cur.row][cur.col]=1; //走回去后把走过的路重新记为1
StackPop(&path); //走错了返回后要删除
}
int main()
{
int M, N, P;
while (scanf("%d %d %d", &M, &N, &P) != EOF)
{
//创建二维数组
int** maze=(int**)malloc(sizeof(int*)*M);
for(int i=0;i<M;i++)
{
maze[i]=(int*)malloc(sizeof(int)*N);
}
//二维数组的输入
for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
scanf("%d ",&maze[i][j]);
}
}
//入口点
PT entry={0,0};
//栈的全局变量的初始化
Stackinit(&path);
Stackinit(&minpath);
//寻找最短路径
GetMazePath(maze,M,N,entry,P);
if(!StackEmpty(&minpath))
{
PrintMaze(&minpath); //打印
}
else
{
printf("Can not escape!");
}
//栈的全局变量的清除
StackDestroy(&path);
StackDestroy(&minpath);
//清除空间
for(int i=0;i<M;i++)
{
free(maze[i]);
}
free(maze);
maze=NULL;
}
return 0;
}
京公网安备 11010502036488号