|
总的来说，这个程序运行得不错，可以任意修改迷宫图，但是有一点儿毛病:第一，如果终点不可达，程序陷入循环状态。改良思想，可以写个判断终点或起点是否合法的方法。也可以给所经过的路径标记，如果所以的点都经过了，则退出程序。其次，在switch分支中，以这样的顺序：下、右、上、左 探索的话，则有些点是无法到达的，如点（18，1），这些点称为盲点，只向一个方向绕过去是永远达到 的。解决思路：让探索既向逆时针探索，又向顺时针探索。以下是代码：（已经测试过，保证正确运行）
package test1;
import java.util.Random;
public class Migong
{
static int maze[][];
Stack <Node> stack =new Stack<Node>();
Random r=new Random();
int count=0+r.nextInt(20);
//long count=100; //在nextPos方法中，用来来回实行case；
int i=1; //在nextPos方法中，用来来回实行case；
String flag="ni"; //在nextPos方法中，用来来回实行case；
//String flag="ni";
public static void main(String []args)
{
Migong mg=new Migong();
maze=mg.initMaze();
//Stack<Node> stackWithPath=mg.findPath( mg.stack,new Position(1,0),new Position(18,19));
//Stack<Node> stackWithPath=mg.findPath( mg.stack,new Position(15,18));
//Stack<Node> stackWithPath=mg.findPath( mg.stack,1));
//Stack<Node> stackWithPath=mg.findPath( mg.stack,new Position(9,9));
//Stack<Node> stackWithPath=mg.findPath( mg.stack,new Position(3,1));
Stack<Node> stackWithPath=mg.findPath( mg.stack,39));
mg.printFindPath(stackWithPath,maze);
}
public boolean jugePos(Position p)
{
if( maze[p.x][p.y]==1)
{
System.out.println("对不起，请输入合法的起点和终点！");
return false;
}
else
return true;
}
public void printFindPath(Stack<Node> st,int maze[][])
{
if(st==null)
{
System.out.println("对不起，栈为null！");
}
else
{
if(!st.isEmpty())
{
while(!st.isEmpty())
{
Node node=st.pop();
maze[node.position.x][node.position.y]=-1;
}
printMaze(maze);
}
else
{
System.out.println("对不起，栈为空值！");
}
}
}
public Stack<Node> findPath(Stack<Node> stack,Position start,Position end)
{
int curstep=1; //当前步骤数目
Position curpos=start; //当前位置
Node node;
if(!jugePos(start)||!jugePos(end))
{
return null;
}
else
{
do
{
if(isPass(curpos))
{
node=new Node(curstep,curpos,1);
stack.push(node);
footPrint(curpos);//这里有些小毛病，就是探索进入死胡同，而需要回溯的时候，显然我们已经打印了这些不该打印的路径，
while(curpos.equals(end))
{
System.out.println("找到出口了，恭喜！");
return stack;
}
curpos=nextPos(curpos,1);
curstep=curstep+1;
}
else
{
if(!stack.isEmpty())
{
node=(Node)stack.peek();
if(node.di<4) //这个地方书上的算法是while，显然是不对的，应该是if；
{
Node n=(Node)stack.pop();
++n.di; //如果di是3的话，由于3<4,满足进入第一个if分支条件，自增后di是4，
//随后实行push，和nextPos，实行nextPos时就是向左探索。
stack.push(n);
curpos=nextPos(n.position,n.di);
}
else //注意，这里不能是if(node.di==4)，也不能是while(di==4)，因为如果那样，
{ //则当di=3时，既满足实行第一个分支，又满足实行第二个分支（因为实行进入第一个if分支后，
//di变成4，又满足了第二个分支的条件，这样就导致di=4时不能实行向左边探索的任务。
markPrint(node.position);
stack.pop();
}
}
}
}while(!stack.isEmpty());
}
if(stack.getLength()==0)
System.out.println("找不到出口！");
return null;
}
public void markPrint(Position p)
{
System.out.println("点("+p.x+","+p.y+")碰壁！");
}
public Position nextPos(Position curpos,int di)
{
Position pos=new Position(curpos.x,curpos.y);
if(flag=="ni"||flag.equals("ni"))
{
switch(di)
{ case 1:{pos.x+=1;break ;}//向下
case 2:{pos.y+=1;break ;}//向右
case 3:{pos.x-=1;break ;}//向上
case 4:{pos.y-=1;break ;}//向左
}
i++;
if(i>=count) //1 50000 100000 150000
{
//flag="shun";
i=1;
}
System.out.println("逆时针：下，右，上，左");
count=0+r.nextInt(20);
}
else if(flag=="shun"||flag.equals("shun"))
{
switch(di)
{ case 2:{pos.x+=1;break ;}//向下
case 1:{pos.y+=1;break ;}//向右
case 4:{pos.x-=1;break ;}//向上
case 3:{pos.y-=1;break ;}//向左
}
i++;
if(i>=count)
{
//flag="luan";
i=1;
}
System.out.println("顺时针：右，下，左，上");
count=0+r.nextInt(30);
}
else
{
switch(di)
{ case 1:{pos.x+=1;break ;}//向下
case 3:{pos.y+=1;break ;}//向右
case 2:{pos.x-=1;break ;}//向上
case 4:{pos.y-=1;break ;}//向左
}
i++;
if(i>=count)
{
//flag="ni";
i=1;
}
System.out.println("乱时针:下，上，右，左");
count=0+r.nextInt(30);
}
return pos;
}
public void footPrint(Position curpos)
{
System.out.print("点("+curpos.x+","+curpos.y+")可通过！");
System.out.println(" ");
}
public boolean isPass(Position curpos)//不仅测试当前位置是否为0，还需要把当前的Position构造成Node，然后
{ //在stack找，看看是不是已经存在该位置，如果是，则该位置不能通过，否则可以通过;
Stack<Node> temSt=stack;
Node thisNode=new Node(curpos);
if(!temSt.isEmpty())
{
return (maze[curpos.x][curpos.y]==0&&!temSt.hasIt(thisNode));
}
else
{
return maze[curpos.x][curpos.y]==0;
}
}
public int[][] initMaze()// 20行,40列,这个数目跟printMaze（)相关。
{
int maze[][]={ // 5 10 15 20 25 30 35 40
{1,1,1},
{0,
{1,//5
{1,//10
{1,//15
{1,0},//20
};
printMaze(maze);
return maze;
}
public void printMaze(int maze[][])
{
for(int i=0;i<20;i++)
{
for(int j=0;j<40;j++)
{
if(maze[i][j]==1)
System.out.print("■");
else if(maze[i][j]==0)
System.out.print("□");
else
System.out.print("＊");
}
System.out.println();
}
}
}
class Node
{
int ord;
Position position;
int di;
public Node(Position p)
{
this.position=p;
}
public Node(int ord,Position p,int di)
{
this.ord=ord;
this.position=p;
this.di=di;
}
@Override
public int hashCode() {
final int PRIME = 31;
int result = 1;
result = PRIME * result + ((position == null) ? 0 : position.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Node other = (Node) obj;
if (position == null) {
if (other.position != null)
return false;
} else if (!position.equals(other.position))
return false;
return true;
}
}
class Position { int x; int y; public Position(){}; public Position(int x,int y) { this.x=x; this.y=y; } @Override public int hashCode() { final int PRIME = 31; int result = 1; result = PRIME * result + x; result = PRIME * result + y; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; final Position other = (Position) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } } （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
