#include<iostream>#include<stack>#include<stdio.h>using namespace std;int maze[10][10];int vis[10][10];int n,m;int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};struct point{ int x,y;} p;stack<point> path,temp;int count;void dfs(int x,int y){ if(x==n-1 && y==m-1)//成功---下面处理路径问题 { cout << "******************路径"<< count << "******************" << endl; while(!path.empty())//将path里面的点取出来，放在temp里面 {//path从栈顶-栈底的方向，路径是从终点-起点的顺序 point p1 = path.top(); path.pop(); temp.push(p1); } while(!temp.empty()) {//输出temp里面的路径，这样刚好是从起点到终点的顺序 point p1 = temp.top(); temp.pop(); path.push(p1);//将路径放回path里面，因为后面还要回溯!!! cout << "(" << p1.x << "," << p1.y << ")" << endl; } return; } if(x<0 || x>=n || y<0 || y>=m) return; for(int i=0;i<4;i )//从4个方向探测 { int nx = x dir[i][0]; int ny = y dir[i][1];//nx,ny：选择一个方向，前进一步之后，新的坐标 if(0<=nx && nx<n && 0<=ny && ny<m && maze[nx][ny]==0 && vis[nx][ny]==0) {//条件：nx,ny没有出界，maze[nx][ny]=0这个点不是障碍可以走，vis[nx][ny]=0说明(nx,ny)没有访问过，可以访问 vis[nx][ny]=1;//设为访问过 p.x = nx; p.y = ny; path.push(p);//让当前点进栈 dfs(nx,ny);//进一步探测 vis[nx][ny]=0;//回溯 path.pop();//由于是回溯，所以当前点属于退回去的点，需要出栈 } }}int main(){ count = 0; freopen("in.txt","r",stdin); p.x = 0; p.y = 0; path.push(p); cin >> n >> m; for(int i=0;i<n;i ) { for(int j=0;j<m;j ) { vis[i][j] = 0; cin >> maze[i][j]; } } dfs(0,0); return 0;}一般任务：1、判断可行，2.输出可行路径。
附带一个in.txt作为迷宫。
5 6
0 1 0 0 0 1
0 0 0 1 0 0
1 0 1 0 0 1
1 0 0 1 0 1
1 1 0 0 0 0
总结：
1.栈的基本用法如下：
头文件：#include<stack>
定义栈：stack<point> path;
元素point p入栈：path.push(x);
栈顶元素出栈：path.pop();
获取栈顶元素：point p1 = path.top();
判断栈空：path.empty();
2.用栈记录路径的时候要采用两个栈的原因有两个：
一是，在到达终点时候，需要将所有元素输出，输出结束之后，还需要将元素放回栈path中，因为本次递归结束之后，还要回溯，如果栈空的话，回溯的时候没有办法进行.所以需要一个临时栈temp，让所有元素出栈，然后放回path.
二是，由于path中自栈顶向栈底，是路径的逆序，需要一个个出栈放入临时栈temp中，在从temp出栈，这样才是从起点到终点的正确顺序的路径.
所以本题需要剪枝。
1.奇偶剪枝。T秒内走到表示，任意一条路径长度一定和曼哈顿距离同奇偶。
2.小小剪枝。如果能走的点<=T，一定不存在路径。
来源：https://www.icode9.com/content-4-297601.html联系客服
