package maze;
//迷宫问题:一个有m*n个房间的迷宫中,有一房间是封闭的,在任何位置均可沿8个方向进
//入未封闭的房间罗密欧在(p,q)方格中,朱丽叶在(r,s)方格中。
//罗密欧在抵达朱丽叶方格前,他必须走遍所有未封闭的房间各一次,而且要使到达朱丽叶方格
//的转弯次数最少,每改变一次转弯方向算作转弯一次
import java.util.Vector;public class Maze { int m=8,n=8;
//0表示没有访问过,1预留给将来使用,2表示禁止访问,3表示罗密欧所在房间,4表示朱丽叶所在房间
int[][] a={{3,2,0,0,0,0,0,0},
   {0,0,0,0,0,0,0,0},
   {0,0,0,0,0,0,2,0},
   {0,0,0,0,0,0,0,0},
   {0,0,0,0,2,0,0,0},
   {0,0,0,0,0,4,0,0},
   {0,0,0,0,0,0,0,0},
   {0,2,0,0,0,0,0,0}};
/*
int[][] a={{3,2,0,0,0,0,0,0},
   {0,0,0,0,4,0,0,0}};*/
int firstX=0,firstY=0;
int endX=1,endY=4; Vector path=new Vector();//保存走过的路径
Vector bestPath=new Vector();//保存最短的路径
int sequence=5;
int layer=0;
int direction1=0,direction2=0;

int sum=1000;//转弯的次数
int curveSum=0;
/*
boolean allVisited()
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(a[i][j]==0)
return false;
return true;
}
*/
boolean isEnd(int x,int y)
{
return (x==endX && y==endY);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Maze maze=new Maze();
maze.backTrace();
}

/**
 * @用迭代回溯法解之
 */
void backTrace()
{
int x=firstX,y=firstY;//罗密欧的起始位置
path.addElement(new Point(x,y));

while(true)
{
if((isEnd(x+1,y) || isEnd(x+1,y+1) || isEnd(x,y+1) || isEnd(x-1,y+1) 
|| isEnd(x-1,y) || isEnd(x-1,y-1) || isEnd(x,y-1) || isEnd(x+1,y-1))
)
{
layer--;
if(curveSum<sum)
sum=curveSum;
System.out.print(curveSum+",");
bestPath=path;
}
direction2=0;  
if(x<m-1 && a[x+1][y]==0)
{
x=x+1;
direction2=1; //right
path.addElement(new Point(x,y));
}
else if(x<m-1 && y<n-1 && a[x+1][y+1]==0)
{
x=x+1;
y=y+1;
direction2=2; //rightDown
path.addElement(new Point(x,y));
}
else if(y<n-1 && a[x][y+1]==0)
{
y=y+1;
direction2=3; //down
path.addElement(new Point(x,y));
}
else if(x>0 && y<n-1 && a[x-1][y+1]==0)
{
x=x-1;
y=y+1;
direction2=4; //leftDown
path.addElement(new Point(x,y));
}
else if(x>0 && a[x-1][y]==0)
{
x=x-1;
direction2=5; //left
path.addElement(new Point(x,y));
}
else if(x>0 && y>0 && a[x-1][y-1]==0)
{
x=x-1;
y=y-1;
direction2=6; //leftUp
path.addElement(new Point(x,y));
}
else if(y>0 && a[x][y-1]==0)
{
y=y-1;
direction2=7; //up
path.addElement(new Point(x,y));
}
else if(x<n-1 && y>0 && a[x+1][y-1]==0)
{
x=x+1;
y=y-1;
direction2=8; //rightUp
path.addElement(new Point(x,y));
}
if(direction1!=direction2)
curveSum++;
direction1=direction2;//保存上一次的方向
if(direction2==0)//not move
{
if(layer==0)  //结束搜索
break;
else
    layer--;

x=((Point)path.elementAt(layer)).x;
y=((Point)path.elementAt(layer)).y;
}
else
layer++;
}
/*
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(a[i][j]+" ");
}
System.out.println();
}
*/
System.out.println();
for(int i=0;i<bestPath.size();i++)
System.out.print(((Point)bestPath.elementAt(i)).x+" "+((Point)bestPath.elementAt(i)).y+", "); System.out.println();
System.out.println(sum);
System.out.print(curveSum);
}}class Point
{
int x;
int y;
Point(int a,int b)
{
x=a;
y=b;
}
}