迷宫求解 C++ 栈

温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。

题目描述

给出一个N*N的迷宫矩阵示意图，从起点[0,0]出发，寻找路径到达终点[N-1, N-1]

要求使用堆栈对象来实现，具体算法参考课本3.2.4节51页

输入

第一行输入t，表示有t个迷宫

第二行输入n，表示第一个迷宫有n行n列

第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过

输入n行

以此类推输入下一个迷宫

输出

逐个输出迷宫的路径

如果迷宫不存在路径，则输出no path并回车

如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾，具体格式参考示范数据

输出的代码参考如下：

//path是保存路径的堆栈，堆栈中每个元素都包含x坐标和y坐标，用属性xp和yp表示 //path1是一个临时堆栈，把path的数据倒序输出到path1，使得路径按正序输出 if (!path.empty())//找到路径 {//......若干代码，实现path的数据导入path1 i=0;  

//以下是输出路径的代码 while (!path1.empty()) {cpos = path1.top(); if ( (++i)%4 == 0 ) cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--"<<endl; else cout<<'['<<cpos.xp<<','<<cpos.yp<<']'<<"--"; path1.pop(); } cout<<"END"<<endl; } else cout<<"no path"<<endl; //找不到路径输出no path

输入样例1 

2 8 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 0 7 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0

输出样例1

[0,0]--[0,1]--[0,2]--[1,2]-- [1,3]--[2,3]--[3,3]--[3,4]-- [4,4]--[5,4]--[5,5]--[6,5]-- [6,6]--[7,6]--[7,7]--END no path

输入样例2 

2 12 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 12 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0

输出样例2

[0,0]--[1,0]--[1,1]--[1,2]-- [1,3]--[1,4]--[1,5]--[1,6]-- [1,7]--[1,8]--[1,9]--[1,10]-- [2,10]--[3,10]--[3,9]--[3,8]-- [3,7]--[3,6]--[3,5]--[3,4]-- [3,3]--[3,2]--[3,1]--[4,1]-- [4,0]--[5,0]--[6,0]--[6,1]-- [6,2]--[6,3]--[6,4]--[6,5]-- [6,6]--[6,7]--[6,8]--[6,9]-- [6,10]--[7,10]--[8,10]--[9,10]-- [9,9]--[9,8]--[10,8]--[11,8]-- [11,9]--[11,10]--[11,11]--END no path

思路分析

先讲一下踩过的坑，原来是可以上下左右移动的，一开始我以为只需要向右和向下就行了。

这道题用回溯法和深度优先遍历解决。

先记录刚开始的位置，这道题是（0，0）。

然后按照优先级，依次判断右边、下边、左边，最后是上边能不能过，如果能过，将新坐标压栈，更新位置，开始下一次探索。

如果四周查遍没有可以过的，判断一下是否已经到达终点，如果还没有到达终点，我们需要返回上一步的位置，此时需要弹栈出来，更新位置为上一次的位置。

其中需要注意，每当我们走过一个可以通过的位置就需要将这个位置标记为不能通过，这样以后回来的时候不会重蹈覆辙。

AC代码 

#include<bits/stdc++.h>
using namespace std;
class Point {
	public:
		int x, y;
		Point(int x, int y): x(x), y(y) {}
};
int main() {
	int t, n, x, y;
	cin >> t;
	while (t--) {
		cin >> n;
		int maze[n][n];
		for (x = 0; x < n; x++)
			for (y = 0; y < n; y++)
				cin >> maze[x][y];
		if (maze[0][0]) {
			cout << "no path" << endl;
			continue;
		}
		stack<Point>track, re_track;
		x = y = 0;
		Point point(0, 0);
		track.push(point);
		while (x < n && y < n) {
			if (y + 1 < n && maze[x][y + 1] == 0) {
				Point point(x, ++y);
				track.push(point);
				maze[x][y] = 1;
				continue;
			} else if (x + 1 < n && maze[x + 1][y] == 0) {
				Point point(++x, y);
				track.push(point);
				maze[x][y] = 1;
				continue;
			} else if (y - 1 >= 0 && maze[x][y - 1] == 0) {
				Point point(x, --y);
				track.push(point);
				maze[x][y] = 1;
				continue;
			} else if (x - 1 >= 0 && maze[x - 1][y ] == 0) {
				Point point(--x, y);
				track.push(point);
				maze[x][y] = 1;
				continue;
			}
			if (x == n - 1 && y == n - 1)break;
			Point point = track.top();
			track.pop();
			if (track.empty())break;
			x = track.top().x;
			y = track.top().y;
		}
		if (track.empty()) {
			cout << "no path" << endl;
			continue;
		}
		while (!track.empty()) {
			re_track.push(track.top());
			track.pop();
		}
		int newline = 0;
		while (!re_track.empty()) {
			if (newline && newline % 4 == 0)
				cout << endl;
			newline++;
			cout << '[' << re_track.top().x << ',' << re_track.top().y << "]--";
			re_track.pop();
		}
		cout << "END" << endl;
	}
}