C++实现简单的走迷宫

一时失言乱红尘 2022-06-17 07:58 212阅读 0赞

**c++实现简单走迷宫**

用n\*n个小方格代表迷宫，每个方格上有一个字符0或1，0代表这个格子不能走，1代表这个格子可以走。只能一个格子一个走，而且只能从一个格子向它的上、下、左、右四个方向走，且不能重复。迷宫的入口和出口分别位于左上角和右下角，存在唯一的一条路径能够从入口到达出口，试着找出这条路径。

例如，下图是一个迷宫，红色表示走出迷宫的一条路径

![Center][]

输入：入口坐标（startX，startY）,出口坐标（endX，endY）

输出：如果存在这样一条路径，则输出1，并输出路径(0,0)->(1,0)->(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)->(5,5)->(4,5)->(4,6)->(4,7)->(5,7)->(6,7)->(7,7)

**思路：利用回溯法求解。**

**首先，根据输入在矩阵中找到路径的起点。假设矩阵中某个格子的字符为1，就往相邻的格子寻找字符为1的格子。** **除了在矩阵边界上的格子之外，每个格子都有4个相邻的格子。重复这个过程直到在矩阵中找到相应的出口位置。**

**当在矩阵中定位了路径上n个格子的位置后，在与第n个格子周围都没有找到第n+1个格子为1，则只好在路径上回到第n-1个格子，重新去寻找第n个字符为1的格子**

**由于路径不能重复进入格子，我们需要定义一个字符矩阵一样大小的布尔值矩阵，用来标记路径是否已经进入了相应格子。**

**代码实现如下：**

#include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution {
    public:
    	bool hasPath(char* matrix, int rows, int cols,  int startX,int startY, int endX, int endY,vector<int>& Path)
    	{
    		if (matrix == NULL || rows < 1 || cols < 1 || startX<0||startY<0||endX<0||endY<0||(startX==endX&&startY==endY))
    			return false;
    		bool* visited = new bool[rows*cols];              //定义一个辅助矩阵，用来标记路径是否已经进入了每个格子
    		memset(visited, 0, rows*cols);
    		int pathLength = 0;
    		if (hasPathCore(matrix, rows, cols, startX, startY, endX, endY, visited, Path))
    		{
    			return true;
    		}
    		delete[] visited;
    		return false;
    	}
    
    	/*此函数用来判断在当前路径满足条件下，相邻格子中是否存在一个格子满足条件*/
    	bool hasPathCore(char* matrix, int rows, int cols, int row, int col, int endX, int endY, bool* visited, vector<int>& Path)
    	{
    		if ((row == endX) && (col == endY)&&(matrix[row*cols+col]=='1'))
    		{
    			Path.push_back(endY);
        		Path.push_back(endX);
    			return true;
    		}
    		bool hasPath = false;
    		if (row >= 0 && row < rows&&col >= 0 && col < cols&&matrix[row*cols + col] == '1' && !visited[row*cols + col])
    		{
    //			++pathLength;
    			visited[row*cols + col] = true;
    			Path.push_back(col);
    			Path.push_back(row);
    			/*如果矩阵格子(row,col)字符为1时，从它的4个相邻格子中寻找下一个字符为1的格子*/
    			hasPath = hasPathCore(matrix, rows, cols, row, col - 1, endX, endY, visited,Path) ||
    				hasPathCore(matrix, rows, cols, row - 1, col, endX, endY, visited,Path) ||
    				hasPathCore(matrix, rows, cols, row, col + 1, endX, endY, visited,Path) ||
    				hasPathCore(matrix, rows, cols, row + 1, col, endX, endY, visited,Path);
    			if (!hasPath)                             //如果没找到，则说明当前第n个格子定位不正确，返回上一个位置重新定位
    			{
    				visited[row*cols + col] = false;
    				Path.pop_back();
    				Path.pop_back();
    			}
    		}
    		return hasPath;
    	}
    };
    
    int main()
    {
    	//	char* matrix = "abcesfcsadee";
    	char* matrix = "1000000110110001101000010111011110100000010000001";        //设置迷宫
    	int startX, startY, endX, endY;
    	cin >> startX >> startY >> endX >> endY;                                   //输入起始结束坐标
    	Solution s;
    	vector<int> Path;
    	bool re = s.hasPath(matrix, 7, 7, startX,startY,endX,endY,Path);
    	cout << re << endl;
    	for (int i = 0; i < Path.size();)
    		cout << "(" << Path[i++] << ',' << Path[i++] << ")" << " ";
    	cout << endl;
    	return 0;
    }

[Center]: /images/20220617/f91991b351f44009adc40a5d59feb193.png