迷宫问题,一般采用回溯法,利用stack节点探测,算法复杂度O(n^2),好像采用队列也可以实现,下片日志再使用队列试试。
package com.xx.dataStructure.stack; enum Direction { east, south, west, north, nothing } class Position { int x; int y; boolean isInPath = false; Direction nextPosDirection; private Position(int x, int y, boolean isInPath, Direction nextPosDirection) { this.x = x; this.y = y; this.isInPath = isInPath; this.nextPosDirection = nextPosDirection; } private static Position[][] positions = new Position[11][11]; static { for (int i = 1; i < positions.length; i++) { for (int j = 1; j < positions[i].length; j++) { positions[i][j] = new Position(i, j, false, Direction.east); } } } public static Position getPosition(int x, int y) { return positions[x][y]; } public boolean isInPath() { return isInPath; } @Override public String toString(){ return "("+x +"," + y + ")"; } } // 迷宫求解 public class Strap { static Stack<Position> stack = new Stack<Position>(100); static { stack.init(); } // true static int[][] strap2 = { { 1,1, 1,1 } , { 1,0, 0 ,1}, { 1,1, 0,1 } , { 1,1, 1,1 } }; // true static int[][] strap3 = { { 1, 1, 1, 1, 1 } , {1, 0, 0, 0, 1 } , {1, 0, 1, 1, 1 } , {1, 0, 0, 0, 1 } , {1, 1, 1, 1, 1 } }; // false static int[][] strap4 = { { 0, 1, 1 }, { 0, 0, 1 }, { 0, 1, 0 } }; // true static int[][] strap10 = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1 }, { 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1 }, { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 }, { 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1 }, { 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1 }, { 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1 }, { 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; static Position getNextPosition(int[][] strap, Position p) { if (p.nextPosDirection == Direction.nothing) return null; if (p.nextPosDirection.compareTo(Direction.east) <= 0 && strap[p.x - 1][p.y] == 0 && !Position.getPosition(p.x - 1,p.y).isInPath()) { p.nextPosDirection = Direction.south; return Position.getPosition(p.x - 1, p.y); } else if (p.nextPosDirection.compareTo(Direction.south) <= 0 && !Position.getPosition(p.x,p.y + 1).isInPath() && strap[p.x][p.y + 1] == 0) { p.nextPosDirection = Direction.west; return Position.getPosition(p.x, p.y + 1); } else if (p.nextPosDirection.compareTo(Direction.west) <= 0 && !Position.getPosition(p.x + 1,p.y).isInPath() && strap[p.x + 1][p.y] == 0) { p.nextPosDirection = Direction.north; return Position.getPosition(p.x + 1, p.y); } else if (p.nextPosDirection.compareTo(Direction.north) <= 0 && !Position.getPosition(p.x,p.y - 1).isInPath() && strap[p.x][p.y - 1] == 0) { p.nextPosDirection = Direction.nothing; return Position.getPosition(p.x, p.y - 1); } return null; } static boolean isTrapCanSolution(int [][] strap,int n){ //访问标记n*n阶数组 0 未在路径 1 在路径上 if (n < 2 || strap.length < 4 || strap.length != n + 2) return false; if (strap[1][1] != 0 || strap[n][n] != 0){ return false; } boolean result = false; stack.init(); try { Position pos = Position.getPosition(1, 1); stack.push(pos); pos.isInPath = true; while(!stack.isEmpty()){ Position p = stack.getTop(); if (p == Position.getPosition(n, n)){ result = true; break; } else { Position nextP = getNextPosition(strap,p); if (nextP == null){ stack.pop(); p.isInPath = false; }else { stack.push(nextP); nextP.isInPath = true; } } } if (stack.isEmpty() ){ System.out.println("can not slove the strap problems; "); } else { stack.traverse(); } } catch (Exception e) { e.printStackTrace(); } return result; } public static void main(String[] args) { isTrapCanSolution(strap10,10); } }
相关推荐
//------------ 栈的顺序存储实现 ------------------------------typedef struct...{ int row; int col;}PosType;typedef struct...{ int step;... s.stacksize=STACK_INIT_SIZE; return OK;}
Python数据结构预算法之栈(Stack)的实现与应用 数据结构预算法.pdf
数据结构 严蔚敏 栈 stack
数据结构 迷宫问题 电子书代码C++ 杭电 #include using namespace std; struct DataType { int x; //行 int y; //列 int pre; //方向 }; struct move { int x; int y; } move[4]={{0,1},{1,0},{0,-1},{-1...
数据结构中stack的详细编码及使用 改代码中包含了stack的初始,添加,删除,修改,销毁以及一些简单应用的代码
迷宫问题 C++语言 数据结构课程设计 class Point //迷宫中点位置的存储结构 { public: int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标 int dir; //0:无效,1:下,2:右,3:上,4:左 }; class ...
数据结构 严蔚敏 C语言版 迷宫 status mazePath(seqStack *S, posType start, posType end) { posType curPos; //current positon int curStep; //the ordinary number sElemType e; curPos = start; curStep ...
迷宫求解
线性表应用——复数四则运算 栈和队列应用——迷宫问题 树和图应用——图遍历生成树演示 查找和排序应用——3阶B-树应用 基于STL数据结构及应用——STL的栈stack类 (代码有参考网络,如有侵权便删)
java数据结构 ArrayList、Stack、Map,为提高效率,未做边界判断(由开发人员保证逻辑上不会出现越界),实现了添加和查询的功能,无修改删除功能
用c语言编写的一个stack程序,实现了进栈,出栈,删除栈顶元素等功能。
介绍数据结构栈(Stack)的概念、特点、优缺点、适用场景和Java示例代码
数据结构那本书上的迷宫问题 Stack::~Stack() //析构函数 { } void Stack::Push(T e) //把元素x压入栈中 { LinkNode *P; P=new LinkNode; P->data=e; P->next=top; top=P; }
数据结构_stack_source
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; } *S.top++=e; return...
第二部分 数据结构 第3章 数据描述 75 3.1 引言 75 3.2 线性表 76 3.3 公式化描述 77 3.3.1 基本概念 77 3.3.2 异常类NoMem 79 3.3.3 操作 79 3.3.4 评价 83 3.4 链表描述 86 3.4.1 类ChainNode 和Chain 86 3.4.2 ...
基于C语言的数据结构-栈stack
数据结构实验用堆栈实现计算器,大二数据结构实验
数据结构实例应用(包含源代码) 一、停车场管理 /*停车场管理队列实现,离开时间比进入时间早的情况没做处理*/ #include "consts.h" #define MAXNUM 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef ...
这个是用c语言实现的一个stack类数据结构的操作。对c语言堆栈更加深入的认识!