<Maze problem and shortest path problem (solved by DFS and backtracking method)> - "Algorithm"

Table of contents

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:

1.4 Simulation implementation of stack:

1.5 Test cases and demonstrations:

1.6 Complete source code:

Second, the shortest path problem of the maze:

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

1.1 Problem description:

1.2 Problem Analysis:

1.3 Function function implementation:

1.4 Simulation implementation of stack:

1.5 Test cases and demonstrations:

1.6 Complete source code:

3. Summary:

Postscript: ●Due to the limited level of the author, the article will inevitably contain errors, please readers to correct, slang into articles, sincerely hope for advice!

           

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!

postscript:
●Because the author's level is limited, the article will inevitably contain errors, please correct the readers and use slang words into articles, and sincerely hope for advice!

           

Tags: Algorithm C dfs logistic regressive

Posted by heckenschutze on Sat, 03 Sep 2022 11:42:17 +0930