#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>#include<string.h>typedef struct postion{ int row;//行 int col;//列}PT;/////////////////////////////////////////typedef PT datatype;//将数据类型改为结构体typedef struct stack{ datatype* a; int top; int capacity;}ST;void stackinit(ST* p);void stackpush(ST* p, datatype x);datatype stacktop(ST* p);void stackpop(ST* p);int stacksize(ST* p);bool stackempty(ST* p);void stackdestroy(ST* p);////////////////////////////////////////void stackinit(ST* p)//栈的初始化{ assert(p); p->a = NULL; p->top = 0; p->capacity = 0;}void stackpush(ST* p, datatype x)//入栈{ assert(p); if (p->top == p->capacity) { int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity; datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity); if (tmp != NULL) { p->a = tmp; p->capacity = newcapacity; } } p->a[p->top] = x; p->top++;}void stackpop(ST* p)//移除栈顶元素{ assert(p); assert(p->top > 0); p->top--;}datatype stacktop(ST* p)//出栈{ assert(p); assert(p->top > 0); return p->a[p->top - 1];}bool stackempty(ST* p)//是否为空{ return p->top == 0;}int stacksize(ST* p)//栈中元素个数{ assert(p); return p->top;}void stackdestroy(ST* p)//内存销毁{ assert(p); free(p->a); p->a = NULL; p->top = 0; p->capacity = 0;}
/// ///////////////////////////////////////
bool ispass(int** maze, int N, int M, PT pos)//现在为1为通道，0为墙壁{ if (pos.row >= 0 && pos.row < N && pos.col >= 0 && pos.col < M && maze[pos.row][pos.col] == 1) { //坐标不越界并且该处位置==1 return true; } else { return false; }}ST path;ST minpath;void stackcopy(ST* minpath, ST* path){ minpath->a = (datatype*)malloc(sizeof(datatype*) * path->capacity); memcpy(minpath->a, path->a, sizeof(datatype) * path->top); minpath->top = path->top; minpath->capacity = path->capacity;}void getmazepath(int** maze, int N, int M, PT cur,int p){ stackpush(&path, cur);//入栈 if (cur.row == 0 && cur.col == M - 1)//出口 { //找到最短路径，更新minpath 要保证体力>=0 if (p >= 0 && stackempty(&minpath) || stacksize(&path) < stacksize(&minpath)) { stackdestroy(&minpath); stackcopy(&minpath, &path);//将path赋给minpath } } maze[cur.row][cur.col] = 2;//先将目前所处位置赋值为2 PT next;
next = cur;//上 next.row -= 1; if (ispass(maze, N, M, next))//判断上的位置是否满足继续的条件 { getmazepath(maze, N, M, next,p-3); }
next = cur;//下 next.row += 1; if (ispass(maze, N, M, next))//判断下的位置是否满足继续的条件 { getmazepath(maze, N, M, next,p); }
next = cur;//左 next.col -= 1; if (ispass(maze, N, M, next))//判断左的位置是否满足继续的条件 { getmazepath(maze, N, M, next,p-1); }
next = cur;//右 next.col += 1; if (ispass(maze, N, M, next))//判断右的位置是否满足继续的条件 { getmazepath(maze, N, M, next,p-1); } maze[cur.row][cur.col] = 1;//恢复公共路径 stackpop(&path); //如果上下左右都不满足就移除栈顶元素}void printpath(ST* ps)//由于此时的path栈要打印出来会倒着出，//所以又重新创建了一个栈，将数据导进去{ ST rpath; stackinit(&rpath); while (!stackempty(ps)) { stackpush(&rpath, stacktop(ps)); stackpop(ps); } while (stacksize(&rpath)>1) { PT top = stacktop(&rpath);//此时数据类型被改为PT printf("[%d,%d],", top.row, top.col); stackpop(&rpath); } PT top = stacktop(&rpath);//此时数据类型被改为PT printf("[%d,%d]", top.row, top.col); stackpop(&rpath); stackdestroy(&rpath);//内存销毁}int main(){ int N = 0; int M = 0; int p = 0; while (scanf("%d%d%d", &N, &M,&p) != EOF)//多组输入 { //动态开辟二维数组 //1.开辟N个指针数组 int** maze = (int**)malloc(sizeof(int*) * N); //2.开辟M个空间 int i = 0; for (i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M); }
int j = 0; for (i = 0; i < N; i++) { for (j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } PT entry = { 0,0 }; stackinit(&path); stackinit(&minpath); getmazepath(maze, N, M, entry, p); if (!stackempty(&minpath))//如果最短路径因为体力问题为0 { printpath(&minpath); } else { printf("Can not escape!"); }
stackdestroy(&path); stackdestroy(&minpath);
//释放空间 //1.释放N个数组指针指向的空间 for (i = 0; i < N; i++) { free(maze[i]); } //2.将N个指针数组整体释放 free(maze); maze = NULL; }
return 0;}
评论