1. 迷宫问题求解
迷宫问题_牛客题霸_牛客网
以上迷宫OJ题曾经是百度某一年的其中一个笔试题，迷宫问题本质就是一个图的遍历问题，从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标，栈记录坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路。
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>// 迷宫坐标结构
typedef struct Position {int row; // 行int col; // 列
}PT;typedef PT STDataType;// 栈的结构--建议使用数组
typedef struct Stack {STDataType* a;int top; // 栈顶int capacity;
}ST, Stack;//typedef struct Stack ST;// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);// 取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);// 判断栈是否为空
bool StackEmpty(ST* ps);// 初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}// 销毁栈
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);// 插入数据之前先检查空间是否足够if (ps->top == ps->capacity){// 空间不够增容int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * new_capacity);if (tmp == NULL){perror("realloc fail!\n");exit(-1);}ps->a = tmp;ps->capacity = new_capacity;}ps->a[ps->top++] = x;
}// 出栈
void StackPop(ST* ps)
{assert(ps);// 栈不能为空assert(!StackEmpty(ps));--ps->top;
}// 取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}// 判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}Stack path; // 路径
/********************************************************//* 迷宫问题https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc */// 示例
/*
输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0输出：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)*/// 打印迷宫
void PrintMaze(int** maze, int N, int M)
{for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%d ", maze[i][j]);}printf("\n");}printf("\n");
}// 输出栈里面的坐标路径
void PrintPath(Stack* ps)
{// path里面的数据倒入rPathStack rPath;StackInit(&rPath);while (!StackEmpty(ps)){StackPush(&rPath, StackTop(ps));StackPop(ps);}while (!StackEmpty(&rPath)){PT top = StackTop(&rPath);printf("(%d,%d)\n", top.row, top.col);StackPop(&rPath);}StackDestroy(&rPath);
}// 可以通过的位置
bool IsPass(int** maze, int N, int M, PT pos)
{if (pos.row >= 0 && pos.row < N&& pos.col >= 0 && pos.col < M&& maze[pos.row][pos.col] == 0){return true;}else{return false;}
}// 路径逻辑函数--N,M行数和列数，cur当前位置
bool GetMazePath(int** maze, int N, int M, PT cur)
{StackPush(&path, cur);// 如果走到出口if (cur.row == N - 1 && cur.col == M - 1)return true;// 探测cur位置的上下左右四个方向PT next; // 定义下一个位置maze[cur.row][cur.col] = 2; // 走过一个格子就把数置为2，也可以不置// 上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}// 下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}// 左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}// 右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}StackPop(&path);return false;
}int main()
{int N = 0, M = 0;while (scanf("%d %d", &N, &M) != EOF){// 动态开辟二维数组int** maze = (int**)malloc(sizeof(int*) * N);for (int i = 0; i < N; ++i){maze[i] = (int*)malloc(sizeof(int) * M);}// 二维数组输入for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){scanf("%d", &maze[i][j]);}}StackInit(&path);// 测试打印迷宫//PrintMaze(maze, N, M);PT entry = { 0, 0 }; // 入口if (GetMazePath(maze, N, M, entry)){//printf("找到通路！\n");PrintPath(&path);}else{printf("没有找到通路！\n");}StackDestroy(&path);for (int i = 0; i < N; ++i){free(maze[i]); // 先free每一行}free(maze); // 再free整个mazemaze = NULL;}return 0;
}
2. 迷宫最短路径求解
地下迷宫_滴滴笔试题_牛客网
本题在曾经是滴滴某一年的笔试题，本题在上一个题的基础上计入了体力值的概念，但是本题还有一个隐藏条件，就是要找出迷宫的最短路径，如下图的两个测试用例，需要找出最短路径，才能通过全部测试用例。
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>// 迷宫坐标结构
typedef struct Position {int row; // 行int col; // 列
}PT;typedef PT STDataType;// 栈的结构--建议使用数组
typedef struct Stack {STDataType* a;int top; // 栈顶int capacity;
}ST, Stack;//typedef struct Stack ST;// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);// 取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);// 判断栈是否为空
bool StackEmpty(ST* ps);// 初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}// 销毁栈
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}// 入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);// 插入数据之前先检查空间是否足够if (ps->top == ps->capacity){// 空间不够增容int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * new_capacity);if (tmp == NULL){perror("realloc fail!\n");exit(-1);}ps->a = tmp;ps->capacity = new_capacity;}ps->a[ps->top++] = x;
}// 出栈
void StackPop(ST* ps)
{assert(ps);// 栈不能为空assert(!StackEmpty(ps));--ps->top;
}// 取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}// 判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}Stack path; // 路径
Stack minpath; // 最短路径
/********************************************************//* 迷宫问题https://www.nowcoder.com/questionTerminal/571cfbe764824f03b5c0bfd2eb0a8ddf */// 打印迷宫
void PrintMaze(int** maze, int N, int M)
{for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%d ", maze[i][j]);}printf("\n");}printf("\n");
}// 输出栈里面的坐标路径
void PrintPath(Stack* ps)
{// path里面的数据倒入rPathStack rPath;StackInit(&rPath);while (!StackEmpty(ps)){StackPush(&rPath, StackTop(ps));StackPop(ps);}while (StackSize(&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** maze, int N, int 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(Stack* ppath, Stack* pcopy)
{pcopy->a = (STDataType*)malloc(sizeof(STDataType) * ppath->capacity);memcpy(pcopy->a, ppath->a, sizeof(STDataType) * ppath->top);pcopy->top = ppath->top;pcopy->capacity = ppath->capacity;
}// 路径逻辑函数--N,M行数和列数，cur当前位置 P体力
void GetMazePath(int** maze, int N, int M, PT cur, int P)
{StackPush(&path, cur);// 如果走到出口if (cur.row == 0 && cur.col == M - 1){// 找到了更短的路径，更新minpathif (P >= 0 && StackEmpty(&minpath)|| StackSize(&path) < StackSize(&minpath)){StackDestroy(&minpath);StackCopy(&path, &minpath);}}// 探测cur位置的上下左右四个方向PT next; // 定义下一个位置maze[cur.row][cur.col] = 2; // 走过一个格子就把数置为2// 上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);
}int main()
{int N = 0, M = 0, P = 0;while (scanf("%d %d %d", &N, &M, &P) != EOF){// 动态开辟二维数组int** maze = (int**)malloc(sizeof(int*) * N);for (int i = 0; i < N; ++i){maze[i] = (int*)malloc(sizeof(int) * M);}// 二维数组输入for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){scanf("%d", &maze[i][j]);}}StackInit(&path);StackInit(&minpath);// 测试打印迷宫//PrintMaze(maze, N, M);PT entry = { 0, 0 }; // 入口GetMazePath(maze, N, M, entry, P);if (!StackEmpty(&minpath)){PrintPath(&minpath);}else{printf("Can not escape!\n");}StackDestroy(&path);StackDestroy(&minpath);for (int i = 0; i < N; ++i){free(maze[i]); // 先free每一行}free(maze); // 再free整个mazemaze = NULL;}return 0;
}
完
