很久没写代码了，主要是现在学了一下JAVA，顺便把上课的内容实现一下。栈实现迷宫问题也就是栈实现dfs，主要是顺便把路径记录在栈里，所以稍微有些复杂，下面是代码：
JAVA实现：
package com.stack;import java.util.Stack;class node{ int x,y,dir; node(int x,int y,int dir){ this.x=x; this.y=y; this.dir=dir; }}public class StackDfs{ private static int[][] move={ {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; public static int path(int[][] maze,Stack s){ node temp=new node(1,1,-1);//一开始标记为-1，方便后面+1后从0开始 s.push(temp); while(!s.isEmpty()){ node now=s.peek(); int x=now.x,y=now.y,dir=now.dir+1;//注意这里dir+1，因为回溯后从下一个方向开始 while(dir<8){ //dir之前的方向之前已经处理过了 int xx=x+move[dir][0]; int yy=y+move[dir][1]; if(maze[xx][yy]==0){ temp=new node(xx,yy,dir); s.push(temp); x=xx; y=yy; maze[x][y]=-1; if(x==6&&y==8){ return 1; }else{ dir=0;//前进一步变化方向从0开始 } }else{ dir++;//变化方向为下一个 } } s.pop();//没有路了就回溯 } return 0; } public static void main(String[] args){ int maze[][]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,1,1}, {1,0,1,1,1,0,1,1,1,1}, {1,1,0,0,1,1,0,0,0,1}, {1,0,1,1,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1,1,1}}; Stack s=new Stack (); int ans=path(maze,s); while(!s.isEmpty()){ node temp=s.pop(); System.out.println(temp.x+" "+temp.y+" "+temp.dir); } }} C++实现：
#include#include #include #include #include #include #include #include #include #include #include using namespace std;const int MAX = 50;int maze[8][10] = { { 1,1,1,1,1,1,1,1,1,1 }, { 1,0,1,1,1,0,1,1,1,1 }, { 1,1,0,1,0,1,1,1,1,1 }, { 1,0,1,0,0,0,0,0,1,1 }, { 1,0,1,1,1,0,1,1,1,1 }, { 1,1,0,0,1,1,0,0,0,1 }, { 1,0,1,1,0,0,1,1,0,1 }, { 1,1,1,1,1,1,1,1,1,1 } };int mov[8][2] = { { 0,1 },{ 1,1 },{ 1,0 },{ 1,-1 },{ 0,-1 },{ -1,-1 },{ -1,0 },{ -1,1 } };typedef struct node { int x, y; int dir;};stack S;bool bound(int x, int y) { if (x < 0 || x >= MAX || y < 0 && y >= MAX) return false; return true;}bool dfs(int sx, int sy,int ex,int ey) { S.push(node{ sx,sy,-1}); while (!S.empty()) { node p = S.top(); int x = p.x, y = p.y,dir=p.dir+1; while (dir < 8) { int xx = x + mov[dir][0]; int yy = y + mov[dir][1]; if (maze[xx][yy] == 0) { S.push(node{ xx,yy,dir }); x = xx; y = yy; maze[x][y] = -1; if (x == ex&&y == ey) { return true; } else { dir = 0; } } else { dir++; } } S.pop(); } return false;}int main() { dfs(1, 1, 6, 8); while(!S.empty()){ node temp = S.top(); S.pop(); cout << temp.x << " " << temp.y << " " << temp.dir << endl; } return 0;}