数据结构 — 迷宫问题

旧城等待， 2022-06-08 11:17 237阅读 0赞

# 迷宫问题 #

# \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ #

**问题描述:给定一个二维数组如下所示，数值1位墙壁，0为可以走的通路，要求找到出口位置，并且找到最短的路径.**

**int arr\[10\]\[10\] =  
\{  
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
0, 0, 0, 0, 0, 0, 0, 0, 1, 1,  
1, 1, 1, 0, 1, 1, 1, 0, 1, 1,  
1, 1, 1, 0, 0, 0, 0, 0, 1, 1,  
1, 1, 1, 1, 1, 1, 0, 0, 1, 1,  
1, 1, 1, 1, 1, 1, 0, 0, 1, 1,  
1, 1, 1, 1, 1, 1, 0, 0, 1, 1,  
1, 1, 1, 1, 1, 1, 0, 0, 1, 1,  
1, 1, 1, 1, 1, 1, 0, 0, 1, 1  
\};**

**解决思想:**

**其实突然拿到该题真的无处下手，我们首先找到最短路径的时候首先就要走完通向出口的每一条路，但是我们走过的路**

**怎么样才能退回来呢？？ 这个时候我们就要用试探法和回溯法合并使用了. 具体如何使用呢？？ 来看下面这个图.**

**![20170923174905212][]**

具体思想有了，然后现在呢我们思考一些细节的问题.

首先我们怎么样避免走回头路呢？ 这个很容易想到就是对你走过的路程做一个标记. 然后每走一次将这个位置的数值置为

所走的步数,以后试探的时候，只需要判断下一个节点是否为0，或者它的数值是否大于自己,如果大于自己那么就继续走，

如果小于自己的值那么那个节点一定会是回头路. 所以这样的方法可以解决如下这种问题:

int arr\[10\]\[10\] =  
\{  
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,  
1, 1, 1, 0, 1, 1, 1, 1, 0, 1,  
1, 1, 1, 0, 1, 1, 1, 1, 0, 1,  
1, 1, 1, 0, 0, 0, 0, 0, 0, 1,  
1, 1, 1, 1, 1, 0, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 0, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 0, 1, 1, 1, 1,  
1, 1, 1, 1, 1, 0, 1, 1, 1, 1  
\};

大致思想已经明白了,最重要的代码实现如下：

**代码实现：**

#include<iostream>
    #include<Windows.h>
    #include<assert.h>
    #include<stack>
    using namespace std;
    
    
    struct pos
    {
    	pos(int i,int j)
    		:row(i)
    		,col(j)
    	{}
    
    	int col;
    	int row;
    };
    
    template<int M,int  N>
    class maze
    {
    public:
    	maze(int array[M][N])
    	{
    		for (int i = 0; i < M; i++)
    		{
    			for (int j = 0; j < N; j++)
    			{
    				arr[i][j] = array[i][j];
    			}
    		}
    	}
    	maze(const maze& T)
    	{
    		for (int i = 0; i < M; i++)
    		{
    			for (int j = 0; j < N; j++)
    			{
    				arr[i][j] = T.arr[i][j];
    			}
    		}
    	}
    	void printminmazepath()
    	{
    		pos cur(0,0);
    		cout << "出口:";
    		while (!q.empty())
    		{
    			cur = q.top();
    			cout<<" < - " << "[" << cur.row << "," << cur.col << "]";
    			q.pop();
    		}
    
    	}
    	void getmazepath(pos enter,int count)
    	{
    		pos cur = enter;
    		pos next = cur;
    		arr[enter.row][enter.col] = count+1;
    		p.push(cur);
    
    		if (cur.row == N - 1)
    		{
    			if (q.empty() || q.size() > p.size())
    			{
    				cout << "找到一个出口为" << "[" << cur.row << "," << cur.col << "]" << endl;;
    				q = p;
    			}
    			cout << endl;
    		}
    		//向上试探
    		next.row -= 1;
    		if (CheckAccess(cur, next))
    		{
    			getmazepath(next, arr[cur.row][cur.col]);
    		}
    
    		//向右试探
    		next = cur;
    		next.col += 1;
    		if (CheckAccess(cur, next))
    		{
    			getmazepath(next, arr[cur.row][cur.col]);
    		}
    
    		//向下试探
    		next = cur;
    		next.row += 1;
    		if (CheckAccess(cur, next))
    		{
    			getmazepath(next, arr[cur.row][cur.col]);
    		}
    
    		//向左试探
    		next = cur;
    		next.col -= 1;
    		if (CheckAccess(cur, next))
    		{
    			getmazepath(next, arr[cur.row][cur.col]);
    		}
    		p.pop();
    		return;
    	}
    
    	bool CheckAccess(pos cur,pos next)
    	{
    		if ((next.row >= 0 && next.row < M)
    			&& (next.col >= 0 && next.col <= N)
    			&& (arr[next.row][next.col] == 0 || arr[cur.row][cur.col] < arr[next.row][next.col]))
    		{
    			return true;
    		}
    		return false;
    	}
    	void print()
    	{
    		cout << "该迷宫的俯视图如下->" << endl;
    		for (int i = 0; i < M; i++)
    		{
    			for (int j = 0; j < N; j++)
    			{
    				cout << arr[i][j] << "  ";
    			}
    			cout << endl;
    		}
    	}
    	
    
    private:
    	int arr[M][N];
    	stack<pos> p;
    	stack<pos> q;
    };
    
    void Test()
    {
    	int arr[10][10] =
    	{
    		1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    		1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    		0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    		1, 1, 1, 0, 1, 1, 1, 1, 0, 1,
    		1, 1, 1, 0, 1, 1, 1, 1, 0, 1,
    		1, 1, 1, 0, 0, 0, 0, 0, 0, 1,
    		1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
    		1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
    		1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
    		1, 1, 1, 1, 1, 0, 1, 1, 1, 1
    	};
    
    	maze<10,10> arr1(arr);
    	arr1.print();
     	arr1.getmazepath(pos(2,0),1);
    	arr1.print();
    	arr1.printminmazepath();
    	system("pause");
    }

运行结果：

**![20170923190125100][]**

[20170923174905212]: /images/20220608/0e0632abe1b14239ad8e36839038e22d.png
[20170923190125100]: /images/20220608/863f2b1de9dc4e729e3da7a434ce9e77.png