【数据结构】之迷宫问题

墨蓝 2022-09-28 11:42 188阅读 0赞

所谓迷宫，就是在一个矩阵中，从开始位置有一条通路可以走到最末尾的位置

先画一个迷宫，格式为txt，和编译的文件夹放在一起

![Center][]

在迷宫中，0表示可以走通的路，而1则表示不可走通的墙

首先定义一个结构体，用来存放行和列

struct Pos
    {
    	size_t row;
    	size_t col;
    };

接下来从文件中获得迷宫 的矩阵

void GetMaze(int *maze, size_t N)
    {
    	FILE *fp = fopen("MazeMap.txt", "r");
    	if (fp == NULL)
    	{
    		throw invalid_argument("Read maze filed");
    	}
    
    	for (size_t i = 0; i < N; ++i)
    	{
    		for (size_t j = 0; j < N;)
    		{
    			char ch = fgetc(fp);
    			if (ch == '0' || ch == '1')
    			{
    				maze[i*N + j] = ch - '0';
    			}
    			else if (ch == EOF)
    			{
    				throw invalid_argument("Maze Error");
    			}
    		}
    	}
    }

然后就要判断迷宫中的每一个坐标的路是否为通路

bool CheckIsAccess(int* maze, size_t N, Pos next)
    {
    	if (maze[next.row*N + next.col] == 0)
    	{
    		return true;
    	}
    	return false;
    }

接下俩对于路径的求解的算法有两种方法，递归和非递归

非递归求解：

bool GetMazePath(int *maze, size_t n, Pos entry, stack<Pos>&path)
    {
    	maze[entry.row*N + entry.col] = 2;
    	Pos cur, next;
    	cur = entry;
    	path.push(entry);
    	while (!path.empty())
    	{
    		cur = path.top();
    
    		if (cur.row == N - 1)
    		{
    			return true;
    		}
    		next = cur;
    
    		next.row += 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.row -= 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.col += 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.col -= 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    		path.pop();
    	}
    	return false;
    }

用递归的方法：

void GetMazePath_R(int *maze, size_t N,Pos entry, stack<Pos>&path,stack<Pos>&shortpath)
    {
    	if (entry.row == N - 1)
    	{
    		if (path.size() < shortpath.size() || shortpath.size() == 0)
    		{
    			shortpath = path;
    		}
    		path.pop();
    		return;
    	}
    	Pos cur, next;
    	cur = entry;
    	next = cur;
    
    	next.row += 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R(maze, N, next, path, shortpath);
    	}
    	next = cur;
    
    	next.row -= 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R((int*)maze, N, next,path, shortpath);
    	}
    
    	next.col += 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R((int*)maze, N, next, path, shortpath);
    	}
    
    	next.col -= 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + next.col] + 1;
    		GetMazePath_R((int*)maze, N, next, path, shortpath);
    	}
    
    	path.pop();
    }

其中的-=1和+=1是表示在一个位置处有四个方向，通过行和列的+1和-1来表示这四个方向。

下面就是完整的代码：

#define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    using namespace std;
    #include<stack>
    
    const int N = 10;
    
    struct Pos
    {
    	size_t row;
    	size_t col;
    };
    
    void PrintMaze(int *maze, size_t N)
    {
    	for (size_t i = 0; i < N; ++i)
    	{
    		for (size_t j = 0; j < N; ++j)
    		{
    			cout << maze[i*N + j] << " ";
    		}
    		cout << endl;
    	}
    	cout << endl;
    }
    
    bool CheckIsAccess(int *maze, size_t N, Pos next)
    {
    	if (maze[next.row*N + next.col] == 0)
    	{
    		return true;
    	}
    	return false;
    }
    
    bool CheckIsAccess(int *maze, size_t N, Pos next, Pos cur)
    {
    	if (next.row < 0 || next.row >= N || next.col < 0 || next.col >= N)
    	{
    		return false;
    	}
    
    	if (maze[next.row*N + next.col] == 0)
    	{
    		return true;
    	}
    	return(maze[next.row*N + next.col]>(maze[cur.row*N + next.col] + 1));
    }
    
    
    void GetMaze(int *maze, size_t N)
    {
    	FILE *fp = fopen("MazeMap.txt", "r");
    	if (fp == NULL)
    	{
    		throw invalid_argument("Read maze filed");
    	}
    
    	for (size_t i = 0; i < N; ++i)
    	{
    		for (size_t j = 0; j < N;)
    		{
    			char ch = fgetc(fp);
    			if (ch == '0' || ch == '1')
    			{
    				maze[i*N + j] = ch - '0';
    				++j;
    			}
    			else if (ch == EOF)
    			{
    				throw invalid_argument("Maze Error");
    			}
    		}
    	}
    }
    
    bool GetMazePath(int *maze, size_t n, Pos entry, stack<Pos>&path)
    {
    	maze[entry.row*N + entry.col] = 2;
    	Pos cur, next;
    	cur = entry;
    	path.push(entry);
    	while (!path.empty())
    	{
    		cur = path.top();
    
    		if (cur.row == N - 1)
    		{
    			return true;
    		}
    		next = cur;
    
    		next.row += 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.row -= 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.col += 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    
    		next.col -= 1;
    		if (CheckIsAccess((int*)maze, N, next) == true)
    		{
    			path.push(next);
    			maze[next.row*N + next.col] = 2;
    			continue;
    		}
    		next = cur;
    		path.pop();
    	}
    	return false;
    }
    
    
    void GetMazePath_R(int *maze, size_t N,Pos entry, stack<Pos>&path,stack<Pos>&shortpath)
    {
    	if (entry.row == N - 1)
    	{
    		if (path.size() < shortpath.size() || shortpath.size() == 0)
    		{
    			shortpath = path;
    		}
    		path.pop();
    		return;
    	}
    	Pos cur, next;
    	cur = entry;
    	next = cur;
    
    	next.row += 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R(maze, N, next, path, shortpath);
    	}
    	next = cur;
    
    	next.row -= 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R((int*)maze, N, next,path, shortpath);
    	}
    
    	next.col += 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + cur.col] + 1;
    		GetMazePath_R((int*)maze, N, next, path, shortpath);
    	}
    
    	next.col -= 1;
    	if (CheckIsAccess((int*)maze, N, next, cur) == true)
    	{
    		path.push(next);
    		maze[next.row*N + next.col] = maze[cur.row*N + next.col] + 1;
    		GetMazePath_R((int*)maze, N, next, path, shortpath);
    	}
    
    	path.pop();
    }
    
    void ReMaze(int* maze)
    {
    	for (size_t i = 0; i < N; ++i)
    	{
    		for (size_t j = 0; j < N; ++j)
    		{
    			if (maze[i*N + j] != 1)
    			{
    				maze[i*N + j] = 0;
    			}
    		}
    	}
    }
    
    stack<Pos>MinPath()
    {
    	int maze[N][N] = { 0 };
    	int curmaze[N][N] = { 0 };
    	GetMaze((int*)maze, N);
    	stack<Pos>path, MinPath, empty;
    
    	while (GetMazePath((int*)maze, N, { 0, 0 }, path))
    	{
    		if (path.size() < MinPath.size()||MinPath.size() == 0)
    		{
    			MinPath = path;
    		}
    
    		ReMaze((int*)maze);
    		maze[path.top().row][path.top().col] = 1;
    		path = empty;
    	}
    	return MinPath;
    }
    
    
    void Test()
    {
    	try
    	{
    		int maze[N][N] = { 0 };
    		int curmaze[N][N] = { 0 };
    		GetMaze((int*)maze, N);
    		stack<Pos>path, shortpath;
    		path.push({ 0, 0 });
    		GetMazePath_R((int*)maze, N, { 0, 0 }, path, shortpath);
    		cout << shortpath.size() << endl;
    	}
    	catch (exception &e)
    	{
    		cout << e.what() << endl;
    	}
    }
    
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }

[Center]: /images/20220708/b1713c88948e4d1c841a70449dd106ad.png