继续应用回溯法解决迷宫问题:
问题赘述一下,从一点出发找到出口即可
package 数据结构及算法.回溯法应用之迷宫问题;
import java.util.Iterator;
import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.Position;
public class Maze implements Application{
private static final byte WALL=0;
private static final byte CORRIDOR=1;//非墙,走廊
private static final byte PATH=9;
private static final byte TRIED=2;
private Position finish;
private byte[][] grid;
public Maze(byte[][]grid,Position finish){
this.finish=finish;
this.grid=grid;
}
@Override
public boolean valid(Position pos) {
if(pos.getRow()>=0&&
pos.getRow()<this.grid.length&&
pos.getColumn()>=0&&
pos.getColumn()<this.grid[0].length&&
grid[pos.getRow()][pos.getColumn()]==this.CORRIDOR){
return true;
}
return false;
}
@Override
public void record(Position pos) {
grid[pos.getRow()][pos.getColumn()]=this.PATH;
}
@Override
public boolean done(Position pos) {
return this.finish.getRow()==pos.getRow()&&this.finish.getColumn()==pos.getColumn();
}
@Override
public void undo(Position pos) {
this.grid[pos.getRow()][pos.getColumn()]=this.TRIED;
}
public String toString(){
String result="";
for(int i=0;i<this.grid.length;i++){
for(int j=0;j<this.grid[0].length;j++){
result+=this.grid[i][j]+" ";
}
result+="\n";
}
return result;
}
@SuppressWarnings("rawtypes")
@Override
public Iterator iterator(Position pos) {
return new MazeIterator(pos);
}
@SuppressWarnings("rawtypes")
private class MazeIterator implements Iterator{
private int row=0;
private int column=0;
private int count=0;
public MazeIterator(Position pos) {
this.row=pos.getRow();
this.column=pos.getColumn();
}
@Override
public boolean hasNext() {
return this.count<4;
}
@Override
public Object next() {
Position nextPosition=new Position();
switch(count){
case 0:nextPosition=new Position(row-1,column);
break;//north
case 1:nextPosition=new Position(row,column+1);
break;//east
case 2:nextPosition=new Position(row+1,column);
break;//south
case 3:nextPosition=new Position(row,column-1);
break;//west
}
count++;
return nextPosition;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
}
初始情况是输入的整个矩阵,1表示可走的,0表示墙
public boolean valid(Position pos)中判断为在矩阵内切非墙有效
在public void record(Position pos)中我让该位置记为9.表示走过
public void undo(Position pos),撤销时与上是逆过程;记为2,
private class QueenIterator implements Iterator为内部类,记录某位置的下一行可选位置,按照北,东,南,西的顺序找
测试程序如下
package 数据结构及算法.回溯法应用之迷宫问题;
import java.util.Scanner;
import 数据结构及算法.回溯法.Application;
import 数据结构及算法.回溯法.BackTrack;
import 数据结构及算法.回溯法.Position;
public class MazeTest {
private byte[][]grid;
public MazeTest(byte[][]grid){
Scanner sc=new Scanner(System.in);
String prompt="请输入四个数字,分别作为迷宫的起始点与终点的row,column坐标!";
System.out.println(prompt);
String s=sc.nextLine();
this.grid=grid;
pocessInput(s);
}
public void pocessInput(String s) {
String[] ss=s.split(" ");
int startR=Integer.parseInt(ss[0]);
int startC=Integer.parseInt(ss[1]);
int finalR=Integer.parseInt(ss[2]);
int finalC=Integer.parseInt(ss[3]);
Position startPosition=new Position(startR,startC);
Position finalPosition=new Position(finalR,finalC);
Application app=new Maze(grid, finalPosition);
BackTrack backTrack=new BackTrack(app);
println("开始为:");
println(app.toString());
if(!app.valid(startPosition)||!app.valid(finalPosition)){
println("failure!");
}
else{
app.record(startPosition);
if(app.done(startPosition)||backTrack.tryToSolve(startPosition)){
println("success");
}
else{
app.undo(startPosition);
println("failure!");
}
}
println("最终为:");
println(app.toString());
}
public void println(String s){
System.out.println(s);
}
public static void main(String[]args){
byte[][] grid={{1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,1,0,1,1,1,1,1,0},
{1,0,0,0,1,0,1,0,1,0,1,0,1},
{1,0,0,0,1,1,1,0,1,0,1,1,1},
{1,1,1,1,1,0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,1,1,1,1,1,1,1}
};
new MazeTest(grid);//测试用例 0 0 6 12
}
}
终于把写的东西弄上来了,希望对和我一样的菜鸟有帮助
分享到:
相关推荐
用回溯法编写的具有图形显示界面的迷宫小游戏 应用turbo C 开发
深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用
在算法设计中很经典的几个算法 包括分支限界法 分治法 动态规划 贪心算法 回溯法 其中包括算法的应用 代码实现 如马踏棋盘、迷宫问题、八皇后问题、0—1背包问题,其中实现了0—1背包问题的各个算法的实现
迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;...
数据结构课程设计题目,课程设计,C语言!
迷宫问题是队列和栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,沿某一方向向前探索,若某处未走过的地点能走通,则到达该处新点,否则试探下一方向;若...
首先分析并指出了迭代法、递归法在多孔材料微结构孔洞标记中的不足之处,然后结合回溯法的思想采用一种新的多孔材料孔洞标记法,并利用迷宫问题具体分析了标记的过程。最后用VC++编程实现了淀粉扫描电子显微镜...
8. (注:提高可不做)栈的应用3(可使用顺序栈或链栈完成):使用递归的回溯法实现迷宫程序(提示:程序分为两大模块,根据数据生成地图,漫游地图) 9.定义并实现循环队列的数据结构。 10.应用队列完成Johnson...
5.5.6 迷宫老鼠 180 5.6 参考及推荐读物 188 第6章 队列 189 6.1 抽象数据类型 189 6.2 公式化描述 190 6.3 链表描述 194 6.4 应用 197 6.4.1 火车车厢重排 197 6.4.2 电路布线 201 6.4.3 识别图元 204 6.4.4 工厂...
第20章 回溯法 20.1 算法思想 20.2 应用 20.2.1 货箱装载 20.2.2 0/1背包问题 20.2.3 最大完备子图 20.2.4 旅行商问题 20.2.5 电路板排列 第21章 分支定界 21.1 算法思想 21.2 应用 21.2.1 货箱装载 21.2.2 0/1背包...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
寻路可视化工具寻路算法是一种帮助你找到两点之间最短路径的算法。 这是一个 react.js 应用程序,它可视... 保证最短路径迷宫算法此应用程序支持以下迷宫算法: 递归除法迷宫递归回溯器随机 Prim' 算法螺旋迷宫随机迷宫
数据结构算法与应用-C__语言描述 目 录 译者序 前言 第一部分 预备知识 第1章 C++程序设计 1 1.1 引言 1 1.2 函数与参数 2 1.2.1 传值参数 2 1.2.2 模板函数 3 1.2.3 引用参数 3 1.2.4 常量引用参数 4 1.2.5 返回值 ...
5.5.6 迷宫老鼠 180 5.6 参考及推荐读物 188 第6章 队列 189 6.1 抽象数据类型 189 6.2 公式化描述 190 6.3 链表描述 194 6.4 应用 197 6.4.1 火车车厢重排 197 6.4.2 电路布线 201 6.4.3 识别图元 204 6.4.4 工厂...
5.5.6 迷宫老鼠 180 5.6 参考及推荐读物 188 第6章 队列 189 6.1 抽象数据类型 189 6.2 公式化描述 190 6.3 链表描述 194 6.4 应用 197 6.4.1 火车车厢重排 197 6.4.2 电路布线 201 6.4.3 识别图元 204 6.4.4 工厂...
回溯 492 16.1 算法思想 492 16.2 应用 496 16.2.1 货箱装船 496 16.2.2 0/1背包问题 503 16.2.3 最大完备子图 506 16.2.4 旅行商问题 508 16.2.5 电路板排列 510 第17章 分枝定界 516 ...
数据结构算法与应用-C++语言描述 目 录 译者序 前言 第一部分 预备知识 第1章 C++程序设计 1 1.1 引言 1 1.2 函数与参数 2 1.2.1 传值参数 2 1.2.2 模板函数 3 1.2.3 引用参数 3 1.2.4 常量引用参数 4 ...