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:
The above maze OJ question used to be one of Baidu's written test questions in a certain year. The essence of the maze question is a traversal problem of a graph. From the starting point, we continue to explore in four directions until we reach the exit. In the process of walking, we walk through the stack record. The coordinates of the path and the coordinates of the stack record have two functions. On the one hand, it records the path traveled, and on the other hand, it is convenient to backtrack to find other paths when reaching a dead end. Four-way recursion is involved here. (recursion in four directions: up, down, left, and right)
Here we analyze and solve with the help of depth-first traversal (DFS) and backtracking.
According to the requirements of the topic, the implementation method is determined after analysis, and the functions of each part are realized in a modularized manner, and then organized according to the method of "high cohesion, low coupling"!
1.3 Function function implementation:
(1) First define the structure of the maze coordinate position:
(2) Write out the calling logic (main function):
(3) Judging the path coordinates can be traversed:
(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:
This question used to be a written test question of Meituan for a certain year. This question includes the concept of physical strength on the basis of the previous question. However, this question also has a hidden condition, which is to find the shortest path of the maze, as shown in the two figures below. For each test case, the shortest path needs to be found to pass all the test cases. This problem is still solved with the help of depth-first traversal (DFS) and backtracking. This involves four-way recursion, (recursion in four directions: up, down, left, and right).
Analyze the problem and determine the solution method:
According to the title, it can be seen that compared with the "maze problem", this question has been "varied" on the basis of the previous question, that is, the "physical strength value" and the shortest path are introduced, and the path has also changed from "only one" to "multiple paths". Therefore, we need to analyze and package each functional module and organize it according to the design principle of "high cohesion, low coupling".
1.3 Function function implementation:
(1) The structure that defines the coordinates of the maze:
(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!