迷宫问题
_____________________________________________
问题描述:给定一个二维数组如下所示&＃xff0c;数值1位墙壁&＃xff0c;0为可以走的通路&＃xff0c;要求找到出口位置&＃xff0c;并且找到最短的路径.
int arr[10][10] &＃61;
{
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
};
解决思想:
其实突然拿到该题真的无处下手&＃xff0c;我们首先找到最短路径的时候首先就要走完通向出口的每一条路&＃xff0c;但是我们走过的路
怎么样才能退回来呢&＃xff1f;&＃xff1f; 这个时候我们就要用试探法和回溯法合并使用了. 具体如何使用呢&＃xff1f;&＃xff1f; 来看下面这个图.
具体思想有了&＃xff0c;然后现在呢我们思考一些细节的问题.
首先我们怎么样避免走回头路呢&＃xff1f; 这个很容易想到就是对你走过的路程做一个标记. 然后每走一次将这个位置的数值置为
所走的步数,以后试探的时候&＃xff0c;只需要判断下一个节点是否为0&＃xff0c;或者它的数值是否大于自己,如果大于自己那么就继续走&＃xff0c;
如果小于自己的值那么那个节点一定会是回头路. 所以这样的方法可以解决如下这种问题:
int arr[10][10] &＃61;
{
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
};
大致思想已经明白了,最重要的代码实现如下&＃xff1a;
代码实现&＃xff1a;
#include
#include
#include
#include
using namespace std;struct pos
{pos(int i,int j):row(i),col(j){}int col;int row;
};template
class maze
{
public:maze(int array[M][N]){for (int i &＃61; 0; i p.size()){cout <<"找到一个出口为" <<"[" <&＃61; 0 && next.row &＃61; 0 && next.col <&＃61; N)&& (arr[next.row][next.col] &＃61;&＃61; 0 || arr[cur.row][cur.col] " < p;stack q;
};void Test()
{int arr[10][10] &＃61;{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");
}
运行结果&＃xff1a;
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号