public class Graphic {
static int floors=5;//楼层数
//先只考虑向上的情况
static int floorNUP[]={3,3,2,4,0};//向上电梯数
static int floorNDOWN[]={0,3,3,2,4};//向下电梯数
public static void main(String[] args){
int Tup[][][]={
{},
{{2,2,2},{4,2,3},{3,4,2}},
{{2,3},{1,3},{2,4}},
{{3,4,4,4},{4,1,2,3}},
{},
};//Tup[i][m][n],i层向上第m个电梯出口到第n个电梯入口的距离,可提供坐标通过astar求出
int Dup[][][][];//Dup[j][m][i][n]第j层m号电梯入口到i层n号电梯出口的最短距离
Dup= new int[10][10][10][10];
int Fup[][][][];//Fup[j][m][i][n]第j层m号电梯入口到i层n号电梯出口的最多路径上,对应j+1层的电梯入口
Fup= new int[10][10][10][10];
int i,j,m,n,x,min;
for(i=2;i<=floors;i++)//从终点i层开始往下算
for(n=0;n<floorNUP[i-2];n++)//扫描i层的所有电梯出口
{
Dup[i-1][n][i][n]=0;//若只相差一层,则距离为0
if(i-2>0)//若相差两层,通过T表直接计算
for(m=0;m<floorNUP[i-3];m++)
{
Dup[i-2][m][i][n]=Tup[i-2][m][n];
System.out.println("Dup"+(i-2)+' '+m+' '+i+' '+n+'='+Dup[i-2][m][i][n]);//输出测试
}
for(j=i-3;j>=1;j--)//相差三层开始使用DP,向下扫描j层
{
for(m=0;m<floorNUP[j-1];m++)//扫描j层所有电梯入口
{
min=62553;
for(x=0;x<floorNUP[j];x++)//扫描j+1层的所有电梯入口
{
if(Dup[j+1][x][i][n] + Dup[j][m][j+2][x]<min)
{
min=Dup[j+1][x][i][n] + Dup[j][m][j+2][x];
Fup[j][m][i][n]=x;
}
}
if(min!=62553)
{
Dup[j][m][i][n]=min;
System.out.println("Dup"+j+' '+m+' '+i+' '+n+'='+min);//输出测试
}
}
}
}
//输出路径时,可通过Fup[j][m][i][n]顺次向上寻找j+1层j+2层……i-2层的电梯入口编号,i-1层电梯入口编号与i层目标出口编号相同
//对了,层数编号是从1开始的,电梯出入口编号都是从0开始
//下面同理 计算所有向下电梯
int Tdown[][][]={
{},
{{2,4,3},{2,2,4},{2,3,2}},
{{2,1,2},{3,3,4}},
{{3,4},{4,1},{4,2},{4,3}},
{},
};//Tdown[i][m][n],i层向上第m个电梯出口到第n个电梯入口的距离,可提供坐标通过astar求出
int Ddown[][][][];//Ddown[j][m][i][n]第j层m号电梯入口到i层n号电梯出口的最短距离
Ddown= new int[10][10][10][10];
int Fdown[][][][];//Fdown[j][m][i][n]第j层m号电梯入口到i层n号电梯出口的最多路径上,对应j-1层的电梯入口
Fdown= new int[10][10][10][10];
for(i=floors-1;i>=1;i--)//从终点i层开始往上算
for(n=0;n<floorNDOWN[i];n++)//扫描i层的所有电梯出口
{
Ddown[i+1][n][i][n]=0;//若只相差一层,则距离为0
if(i+2<=floors)//若相差两层,通过T表直接计算
for(m=0;m<floorNDOWN[i+1];m++)
{
Ddown[i+2][m][i][n]=Tdown[i][m][n];
System.out.println("Ddown"+(i+2)+' '+m+' '+i+' '+n+'='+Ddown[i+2][m][i][n]);//输出测试
}
for(j=i+3;j<=floors;j++)//相差三层开始使用DP,向上扫描j层
{
for(m=0;m<floorNDOWN[j-1];m++)//扫描j层所有电梯入口
{
min=62553;
for(x=0;x<floorNDOWN[j-2];x++)//扫描j-1层的所有电梯入口
{
if(Ddown[j-1][x][i][n] + Ddown[j][m][j-2][x]<min)
{
min=Ddown[j-1][x][i][n] + Ddown[j][m][j-2][x];
Fdown[j][m][i][n]=x;
}
}
if(min!=62553)
{
Ddown[j][m][i][n]=min;
System.out.println("Ddown"+j+' '+m+' '+i+' '+n+'='+min);//输出测试
}
}
}
}
}
}