当前位置: 代码迷 >> 综合 >> 栈实现迷宫问题
  详细解决方案

栈实现迷宫问题

热度:53   发布时间:2024-01-16 13:26:07.0

很久没写代码了,主要是现在学了一下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<node> 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<node> s=new Stack<node>();int ans=path(maze,s);while(!s.isEmpty()){node temp=s.pop();System.out.println(temp.x+"  "+temp.y+"  "+temp.dir);}}
}

C++实现:

#include<iostream>
#include<cstdio>
#include<string>
#include<regex>
#include<iomanip>
#include<iterator>
#include<random>
#include<ctime>
#include<stack>
#include<vector>
#include<algorithm>
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<node> 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;
}


  相关解决方案