Table of contents

1. Maze problem link: (Nioke.com) Maze problem

1.3 Function function implementation:

1.4 Simulation implementation of stack:

1.5 Test cases and demonstrations:

Second, the shortest path problem of the maze:

1. Link to the shortest path problem of the maze: (Nioke.com) Underground Maze

1.3 Function function implementation:

1.4 Simulation implementation of stack:

1.5 Test cases and demonstrations:

# First, the maze problem:

## 1. Maze problem link: (Nioke.com) maze problem

### 1.1 Problem description:

### 1.2 Problem Analysis:

### 1.3 Function function implementation:

(4) Determine whether the coordinate is a valid traversable coordinate

(5) Output the coordinate path in the stack:

Due to the "FIFO" nature of the stack, and the problem requires printing from the very beginning, the order needs to be adjusted.

(6) Print the traversed path coordinates:

### 1.4 Simulation implementation of stack:

(Here, with the help of the "FIFO" nature of the stack, the stack is used to store the data storage for recursive traversal, and the coordinates that do not match are popped out of the stack, and then backtracked traversal is performed)

### 1.5 Test cases and demonstrations:

Example 1:

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

Example 2:

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

Test print:

### 1.6 Complete source code:

#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<string.h> //Define the location structure typedef struct Postion { int row; int col; }PT; / //Implementation of stack typedef PT STDataType; typedef struct Stack { STDataType* a; //Implement stack structure through arrays int top; int capacity; }ST; //initialization void StackInit(ST* ps); //Free up memory, destroy space void StackDestory(ST* ps); // push onto the stack void StackPush(ST* ps, STDataType x); // pop void StackPop(ST* ps); //Get the top of the stack STDataType StackTop(ST* ps); //stack size int StackSize(ST* ps); //Empty bool StackEmpty(ST* ps); //initialization void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); exit(-1); } ps->capacity = 4; ps->top = 0; //This makes top end up pointing to a location after the top of the stack. If top=-1, it will eventually point to the top of the stack. } //Free up memory, destroy space void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } // push onto the stack void StackPush(ST* ps, STDataType x) { assert(ps); // full -> capacity increase if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail!\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } // pop void StackPop(ST* ps) { assert(ps); // The stack is empty, and calling Pop again will directly stop the program and report an error assert(ps->top > 0); //ps->a[ps->top - 1] = 0; //Setting to 0 only considers int type, etc., if it is char, double, etc., it does not apply. ps->top--; } //Get the top of the stack STDataType StackTop(ST* ps) { assert(ps); // The stack is empty, and calling Top again will directly stop the program and report an error assert(ps->top > 0); return ps->a[ps->top - 1]; } //find stack size int StackSize(ST* ps) { assert(ps); return ps->top; } //Empty bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //maze implementation ST path; //define global variables //Print 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"); } // The coordinate path in the output stack //It is required to output from the first coordinate, and the stack is last in first out, and the output needs to be adjusted void PirntPath(ST* ps) { // path data is poured to rPath ST rPath; StackInit(&rPath); while (!StackEmpty(&path)) { StackPush(&rPath, StackTop(&path)); StackPop(&path); } while (!StackEmpty(&rPath)) { PT top = StackTop(&rPath); printf("(%d,%d)\n", top.row, top.col); StackPop(&rPath); } StackDestory(&rPath); } //Determine whether the coordinate is a valid traversable coordinate 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; } } //Judging the path coordinates can be traversed bool GetMazePath(int** maze, int N, int M, PT cur) { StackPush(&path, cur); // If you go to the exit if (cur.row == N - 1 && cur.col == M - 1) return true; // Detect the cur position in four directions: up, down, left and right PT next; maze[cur.row][cur.col] = 2; //The position that has been traversed (including the current), marked as 2 //traverse up next = cur; next.row -= 1; if (IsPass(maze, N, M, next)) { if (GetMazePath(maze, N, M, next)) return true; } //Traverse down next = cur; next.row += 1; if (IsPass(maze, N, M, next)) { if (GetMazePath(maze, N, M, next)) return true; } //Traverse left next = cur; next.col -= 1; if (IsPass(maze, N, M, next)) { if (GetMazePath(maze, N, M, next)) return true; } //traverse right next = cur; next.col += 1; if (IsPass(maze, N, M, next)) { if (GetMazePath(maze, N, M, next)) return true; } StackPop(&path); //No, this coordinate cannot be used, just pop the stack return false; //If the four directions do not work, return false, and the recursion will backtrack and explore other paths. } int main() { int N = 0, M = 0; while (scanf("%d%d", &N, &M) != EOF) { // int a[n][m]; // not supported by vs2013 // Dynamically open up a two-dimensional array int** maze = (int**)malloc(sizeof(int*) * N); for (int i = 0; i < N; ++i) { maze[i] = (int*)malloc(sizeof(int) * M); } // 2D array input 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 }; //Entrance if (GetMazePath(maze, N, M, entry)) { //printf("Find the path\n"); PirntPath(&path); } else { printf("no way found\n"); } StackDestory(&path); for (int i = 0; i < N; ++i) { free(maze[i]); } free(maze); maze = NULL; } return 0; }

# Second, the shortest path problem of the maze:

## 1. Link to the shortest path problem in the maze: (Nioke.com) Underground Labyrinth

### 1.1 Problem description:

### 1.2 Problem Analysis:

### 1.3 Function function implementation:

(2) Write out the calling logic (main function):

(3) Obtain valid path coordinates for valid traversal:

(4) Solve the problem that an error will be reported when the shallow copy is released twice:

(5) Determine whether the coordinate is a valid traversable coordinate:

(6) Output the path coordinates stored in the stack:

Due to the "FIFO" nature of the stack, and the problem requires printing from the very beginning, the order needs to be adjusted.

(7) Print the valid path coordinates of the traversal:

### 1.4 Simulation implementation of stack:

(Here, with the help of the "FIFO" nature of the stack, the stack is used to store the data storage for recursive traversal, and the coordinates that do not match are popped out of the stack, and then backtracked traversal is performed)

### 1.5 Test cases and demonstrations:

Example 1:

### 1.6 Complete source code:

//2. Maze shortest path problem #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<string.h> //A structure that defines the coordinates of the maze typedef struct Postion { int row; int col; }PT; / //Implementation of stack typedef PT STDataType; typedef struct Stack { STDataType* a; //Implement stack structure through arrays int top; int capacity; }ST; //initialization void StackInit(ST* ps); //Free up memory, destroy space void StackDestory(ST* ps); // push onto the stack void StackPush(ST* ps, STDataType x); // pop void StackPop(ST* ps); //Get the top of the stack STDataType StackTop(ST* ps); //stack size int StackSize(ST* ps); //Empty bool StackEmpty(ST* ps); //initialization void StackInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); exit(-1); } ps->capacity = 4; ps->top = 0; //This makes top end up pointing to a location after the top of the stack. If top=-1, it will eventually point to the top of the stack. } //Free up memory, destroy space void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } // push onto the stack void StackPush(ST* ps, STDataType x) { assert(ps); // full -> capacity increase if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail!\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } // pop void StackPop(ST* ps) { assert(ps); // The stack is empty, and calling Pop again will directly stop the program and report an error assert(ps->top > 0); //ps->a[ps->top - 1] = 0; //Setting to 0 only considers int type, etc., if it is char, double, etc., it does not apply. ps->top--; } //Get the top of the stack STDataType StackTop(ST* ps) { assert(ps); // The stack is empty, and calling Top again will directly stop the program and report an error assert(ps->top > 0); return ps->a[ps->top - 1]; } //find stack size int StackSize(ST* ps) { assert(ps); return ps->top; } //Empty bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //maze implementation ST path; //define global variables ST minpath; //define the shortest path //Print 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"); } // The coordinate path in the output stack //It is required to output from the first coordinate, and the stack is last in first out, and the output needs to be adjusted void PirntPath(ST* ps) { // path data is poured to rPath ST rPath; StackInit(&rPath); while (!StackEmpty(ps)) { StackPush(&rPath, StackTop(ps)); StackPop(ps); } //The output is divided into two types, only because of the title requirements, there is no specific meaning here 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); StackDestory(&rPath); } //Determine whether the coordinate is a valid traversable coordinate 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; } } //Solve the problem of two free space errors for shallow copy void StackCopy(ST* ppath, ST* 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; } //Get path coordinates that can be efficiently traversed void GetMazePath(int** maze, int N, int M, PT cur,int P) { StackPush(&path, cur); // If you go to the exit if (cur.row == 0 && cur.col == M - 1) { // Find a shorter path, update minpath; //P is the physical value required by the question, which is required to be within the valid range if (P >= 0 && StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath)) { StackDestory(&minpath); StackCopy(&path, &minpath); } } // To detect the cur position, there are four directions: up, down, left and right PT next; maze[cur.row][cur.col] = 2; //already traveled, marked as 2 //traverse up next = cur; next.row -= 1; if (IsPass(maze, N, M, next)) { (GetMazePath(maze, N, M, next, P - 3)); } //Traverse down next = cur; next.row += 1; if (IsPass(maze, N, M, next)) { (GetMazePath(maze, N, M, next, P)); } //Traverse left next = cur; next.col -= 1; if (IsPass(maze, N, M, next)) { (GetMazePath(maze, N, M, next, P - 1)); } //traverse right next = cur; next.col += 1; if (IsPass(maze, N, M, next)) { (GetMazePath(maze, N, M, next, P - 1)); } //Recursion will backtrack and explore other paths //need to restore 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) { //Create a maze, get a maze map // int a[n][m]; // not supported by vs2013 // Dynamically open up a two-dimensional array int** maze = (int**)malloc(sizeof(int*) * N); for (int i = 0; i < N; ++i) { maze[i] = (int*)malloc(sizeof(int) * M); } // 2D array input 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 }; // Default [0,0] is the entry, [N-1][M-1] is the exit GetMazePath(maze, N, M, entry, P); //Get the valid path traversed to if (!StackEmpty(&minpath)) { PirntPath(&minpath); } else { printf("Can not escape!\n"); } StackDestory(&path); StackDestory(&minpath); //destroy the maze for (int i = 0; i < N; ++i) { free(maze[i]); } free(maze); maze = NULL; } return 0; }

# 3. Summary:

Through the maze problem and the shortest path problem, the depth-first traversal (DFS) and the backtracking method are used to solve the problem, which involves four-way recursion (recursion in four directions: up, down, left, and right). However, the solution is on the one hand, the solution tool Also on the other hand. Here, C language is used to solve the problem. With the help of the nature of the stack in the data structure, the data storage in the process of deep traversal is realized, and then backtracking. Using the C language involves the operation of two-dimensional arrays. Here, two-level pointers and pointer arrays are used. In the comparison and update of the shortest path, the problem of deep and shallow copying is involved. Attention is also required here, otherwise the program will crash!

There are many ways to solve these problems, and there are many tools to solve them, so I won't list them all here!

Finally, pay tribute to the wisdom of the predecessors! Scholars also have a heart of awe! Also cherish the opportunity and time to learn!