Maze search of stack structure

Using stack structure to backoff to solve maze routing problem

The path found is just a path to the destination

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//Searching in array: position -- > row and column
struct position
{
	int row;
	int cols;
};
struct position pathStack[100];		//Stack memory (storage path)
int stackTop = -1;					//Top tag
int** maze = NULL;					//Two dimensional array to describe map
int size = 0;						//Maze size
int** makeArray(int row, int cols)  //Second level pointer to 2D array
{
	int** array = (int**)malloc(sizeof(int*) * row);  
	for (int i = 0; i < cols; i++)
	{
		array[i] = (int*)malloc(sizeof(int) * cols);
	}
	return array;
}
//User enters a maze
void createMaze()
{
	printf("Enter maze size:");
	scanf("%d", &size);
	maze = makeArray(size + 2, size + 2);//Plus 2 for border
	printf("Input maze:\n");
	for (int i = 1; i <= size; i++)
	{
		for (int j = 1; j <= size; j++)
		{
			scanf("%d", &maze[i][j]);
		}
	}
	//Border 1 means wall, can't go
	for (int i = 0; i <= size + 1; i++)
	{
		//First and size+2
		maze[0][i] = 1;
		maze[size + 1][i] = 1;
		//Columns 1 and size+2
		maze[i][0] = 1;
		maze[i][size + 1] = 1;
	}
}
//Finding path
int findPath()
{
	 //Offset description
	struct position offset[4];     //0-3 indicates 4 different directions
	//Offset = > direction
	//Walk to the right.
	offset[0].row = 0;
	offset[0].cols = 1;
	//Go down
	offset[1].row = 1;
	offset[1].cols = 0;
	//Go to the left.
	offset[2].row = 0;
	offset[2].cols = -1;
	//Go up
	offset[3].row = -1;
	offset[3].cols = 0;
	//Equivalent = > struct position offset [4] = {0,1}, {1,0}, {0, - 1}, {- 1,0};
	//Selected entry
	struct position here = { 1,1 };//Current position coordinates
	//Maze = > record the path
	//The place to walk is marked as 1
	maze[1][1] = 1;
	int option = 0;		//Next move direction
	int endOption = 3;	//Termination direction
	while (here.row != size || here.cols != size)//The destination is (size,size)
	{
		//When the destination is not reached, continue to walk
		int rowNum, colsNum;		//Record subscript changes
		while (option <= endOption)
		{
			//Row and column change = original position + offset value (the offset value is determined by the direction)
			rowNum = here.row + offset[option].row;
			colsNum = here.cols + offset[option].cols;
			//Once you have a direction to go, you need to go to the next step
			if (maze[rowNum][colsNum]==0)
			{
				break;  //Can go, exit the cycle, go to the next position
			}
			else//Can't walk. Test in a different direction
			{
				option++;
			}
		}
		//When you jump out of the top, there may be a break (when option < = endoption). In this case, there is a way to go
		//It can also be caused by the fact that option > endoption no longer satisfies the while loop condition. In this case, there is no way to go
		if (option <= endOption)//There's a way
		{
			//Go to the next
			pathStack[++stackTop] = here;
			//Change current position
			here.row = rowNum;
			here.cols = colsNum;
			//Path mark passed = > blocked
			maze[rowNum][colsNum] = 1;
			option = 0;		//Set the starting direction to zero to find the next position
		}
		else//At this time, option > endoption (option equals 4), there is no way to go. Next, step back (go back to the previous step)
		{
			//Go back to the previous step
			if (stackTop == -1) return 0;//Stack is empty, no way to go (no path)
			struct position next = pathStack[stackTop--];//Out of stack = > back to the previous step
			//Direction processing
			if (next.row == here.row)//No change, left or right
			{
				option = (2 + next.cols - here.cols) % 4;
			}
			else//If the row changes, the column does not change. Up and down.
			{
				option = (3 + next.row - here.row) % 4;
			}
			here = next;   //Position fallback to previous position
		}
	}
	return 1;
}

//Print path
void printPath()
{
	if (stackTop == -1)
	{
		printf("No way to go\n");
	}
	else
	{
		printf("Path mode:\n");
		struct position curPos;
		while (stackTop != -1)
		{
			curPos = pathStack[stackTop--];
			printf("(%d,%d)-->", curPos.row, curPos.cols);
		}
		printf("\n");
	}
}
int main()
{
	createMaze();
	if (findPath())	printPath();
	else printf("No way to go!\n");
	return 0;
}


Idea: start from the starting point, and follow the right, down, left and up directions (offsets) to find the way. As long as the value of the offset position is zero, it will pass. Each time a location is reached, the location is stacked and the value of the two-dimensional array of that location is set to 1 to mark that it has passed. If there is no way to go around a point, backout the stack.

Core: findPath(); function

Direction processing:


The handling of directions here is not easy to understand:

When there is no way to walk in all four directions of a location (that is, all four directions of the location are marked as 1), it is necessary to backout the stack.

The first is the fallback of the location: fallback to the previous location of the location.

Next is the direction fallback: at this time, if we set the direction option to 0, it will not affect the search results, but will reduce the search efficiency.

When we change the backward position to the next direction where there is no way to go. It is more efficient because it avoids trying the impossible direction.

As follows:

  • When the line is unchanged, it means that it moves left and right. When moving from left to right, next.cols - here.cols=-1, the direction after fallback should be 1; when moving from right to left, next.cols - here.cols=1, the direction after fallback should be 3. To sum up, the direction after fallback should be: option = (2 + next. Cols - here. Cols)% 4;

  • When rows change, columns do not change. This should be for up and down movement. When moving from bottom to top, next.row - here.row=1, the direction after fallback should be 0; when moving from top to bottom, next.row - here.row=-1, the direction after fallback should be 2. To sum up, the direction after fallback should be: option = (3 + next. Row - here. Row)% 4;

Published 26 original articles, won praise 8, visited 1838
Private letter follow

Posted on Thu, 16 Jan 2020 07:42:35 -0800 by hsn