学步园

Description

有一座10层高的建筑物，搬运工小李需要搬运一些相同的包裹来往于各楼层之间。小李可以不搬运任何包裹而上楼下楼，也可以在搬运某一包裹的途中停下来，将该包裹放在他所处的楼层，然后去做其他的事情。小李从一层开始工作，并且工作结束后他必须返回一层。 现在请你编写一个程序，求出小李完成工作所需的最少上楼层数m（下楼层数不计），并且输出其搬运路径。

Input

输入数据的第一行有一个正整数k（0 < k< =50），表示搬运工所需搬运的包裹数。 接下来有k行，每行有两个整数（整数之间用一个空格分开）。第s（2< =s< =k+1）行的两个整数i，j（1< =i，j<= 10），表示s-1号包裹需要从第i层搬运到第j层。

Output

输出数据的第一行是一个整数m，表示搬运工完成工作所需的最少上楼层数。 接下来输出搬运工的搬运路径，每行有3个整数x，y，z（每两个整数之间用一个空格分开）。x表示搬运z号包裹的出发楼层；y表示搬运z号包裹的终止楼层；z表示被搬运包裹的编号，若z为0，则表示搬运工没有搬运任何包裹而上楼下楼。

Sample Input

2
2 5
8 10

Sample Output

9
1 2 0
2 3 1
3 4 1
4 5 1
5 6 0
6 7 0
7 8 0
8 9 2
9 10 2
10 9 0
9 8 0
8 7 0
7 6 0
6 5 0
5 4 0
4 3 0
3 2 0
2 1 0

HINT

Source

题目分析：

              本题是一个关于包裹投递的问题。题目给出一些包裹的投递要求，需要搬运工小李在一个10层高的建筑物中完成这些包裹的投递任务，要求找出一个最优的搬运方案，使得搬运工小李完成全部工作任务而所上楼的层数最少。从题目所给出的条件来看，搬运货物的路径不是很长，即建筑物的高度只有10层;但是需要搬运的包裹却比较多，最多会有50个包裹，故整个问题的搜索量会很大，搜索算法的时间复杂度很高，不是一个有效的算法。仔细分析题目中的条件，我们可以将问题转化为一个图，从而运用关于图的算法来解决这个问题。

            题目只要求找到上楼层数最少的方案，并没有对上楼方案有其他限制，而且在处理某一个包裹的投递任务时，可以在中途暂停这一任务，而去处理其他的包裹投递任务，这样我们就可以把一个包裹的投递任务（上n层楼或下n层楼）分成若干个简单的投递路线（只上一层楼或者只下一层楼）。如此我们就可以把问题用一个图来表示出来，图的顶点表示楼层，图的边表示投递路线。由于每上一层楼；每下一层楼，也必然要先上一层楼，所以图中的边是具有对应关系的。构造出这个图之后，问题就变得十分简单了，很容易就可以求出上楼的最少楼层数和最优的投递方案。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 11
int floors=10;//总的楼层数
int uptable[N],downtable[N],Eup[N],Edown[N];//存储转化问题后的图
int k,i,m;
int floor;
int package[51][3];//存储包裹的投递任务

void createtable()//构造问题转化为图
{
    int i,j;
    memset(uptable,0,sizeof(uptable));//初始化数组
    memset(downtable,0,sizeof(downtable));
    for(i=1; i<=k; i++)
    {
        if(package[i][1]==package[i][2])continue;//第i层没任务
        if(package[i][1]<package[i][2])//有任务，是要上楼的，统计uptable的次数
        {
            for(j=package[i][1]; j<package[i][2]; j++)
            {
                uptable[j]++;//统计
            }
        }
        else
        {
            for(j=package[i][2]; j>package[i][1]; j--)
            {
                downtable[j]++;//如果是要下楼，统计downtable的次数
            }
        }
    }
    for(i=1; i<=floors; i++)//存储，待用
    {
        Eup[i]=uptable[i];
        Edown[i]=downtable[i];
    }
    for(i=1; i<=floors; i++)//下楼和上楼的次数需要相同，因此uptable[i]和downtable[i]都需要取可能的最大值
    {
        if(uptable[i]>downtable[i])
        {
            downtable[i]=uptable[i];
        }
        else
        {
            uptable[i]=downtable[i];
        }
    }
    for(i=floors-1; i>=1; i--)//检查有没有楼层是不需要搬货物而走上去的
    {
        if(uptable[i]==0&&uptable[i+1]!=0)//有
        {
            uptable[i]=1;
            downtable[i]=1;
        }
    }
    m=0;
    for(i=1; i<=floors; i++)//统计一共要往上走的总层数
    {
        m+=uptable[i];
    }
    printf("%d\n",m);//输出
    return ;
}

void output(int x,int y,int z)//输出一步
{
    printf("%d %d %d\n",x,y,z);
}

int upstair(int f)//上一层楼
{
    int i,bb;
    int p;
    floor=f;
    if(uptable[floor]==0)return 0;//判断能否上楼
    bb=1;
    p=0;
    for(i=1; i<=k; i++)//检查所有在floor层的需要往上搬的货物，找出目标地所在层次最高的货物，记住货物p
    {
        if(package[i][1]==floor&&(package[i][1]<package[i][2]))
        {
            if(p==0)p=i;
            else if(package[p][2]<package[i][2])p=i;
            bb=0;
        }
    }
    if(bb==1)//如果floor层没有需要往上搬的货物，则看floor层上面还有没有货物来决定需不需要往上走
    {
        if(Eup[floor]==uptable[floor]) return 0;
        else
        {
            output(floor,floor+1,0);//不搬货物往上走一层
        }
    }
    else
    {
        package[p][1]++;//货物被搬上了一层，更新其所在层数
        output(floor,floor+1,p);//搬货物p往上走一层
        Eup[floor]=Eup[floor]-1;
    }
    uptable[floor]=uptable[floor]-1;//需要往上走的层数减1
    floor++;//层数加1
    return 1;//返回成功往上走一层
}

int downstair(int f)//下一层楼
{
    int i,bb,p;
    floor=f;
    if(floor==1)return 0;
    if(downtable[floor-1]==0)return 0;//判断是否能下楼
    bb=1;
    p=0;
    for(i=1; i<=k; i++)//检查所有在floor层的需要往下搬的货物，找出目标地所在层次最低的货物，即为货物p
    {
        if(package[i][1]==floor&&(package[i][1]>package[i][2]))
        {
            bb=0;
            if(p==0)p=i;
            else if(package[i][2]>package[i][1])p=i;
        }
    }
    if(bb==1)//如果floor层没有需要往下搬的货物，则看floor层下面还有没有货物来决定需不需要往下走
    {
        if(Edown[floor-1]==downtable[floor-1])return 0;
        else
        {
            output(floor,floor-1,0);
        }
    }
    else
    {
        Edown[floor-1]--;
        package[p][1]--;//货物被搬下了一层，更新其所在层数
        output(floor,floor-1,p);//搬货物p往下走一层
    }
    downtable[floor-1]=downtable[floor-1]-1;//需要往下走的层数减1
    floor--;//所在层减1，到了下一层
    return 1;//返回
}
int main()
{
    int i;
    scanf("%d",&k);
    for(i=1; i<=k; i++)
    {
        scanf("%d%d",&package[i][1],&package[i][2]);
    }
    createtable();//构造图

    floor=1;//从第1层开始
    while(1)
    {
        if(upstair(floor)==0)//上楼
            if(downstair(floor)==0)//下楼
            {
                if(floor!=1)
                {
                    printf("Error!\n");
                }
                else break;
            }
    }
    return 0;
}