首页 > 代码库 > POJ_1208_模拟

POJ_1208_模拟

题目描述:

  给定一个长度n,有0~n-1编号的箱子和位置,起始个编号的箱子放在相同编号的位置。

  有一系列操作:

  move a onto b,将a,b上面的箱子放回初始位置,并将a放到b箱上。

  move a over b ,将a上面的箱子放回初始位置,并将a放到b箱最上方。

  pile a onto b ,将b上面的箱子放回初始位置,并将a和a上的箱子一起放到b箱上。

  pile a over b,将a和a上的箱子一起放到b箱最上方。

  要求输出最后每个位置的箱子。

 

思路:

  要注意的是,当一个位置的初始箱子移走之后,因为这里没有箱子,其他箱子也不会移到这个位置,这样就简单了很多。

  一步步模拟,用了list容器,运行时间应该比用数组长了一些。

  刚开始提交的时候一直Runtime Error,猜想是存在哪个数组越界的情况,但一直找不到错误。然后写了一个随机数组生成的程序测试,发现了问题所在。因为直接用gets读取了一正行操作,只考虑了a和b是一位数的情况,然后就GG了。修改之后,分别用字符串和整形读取操作中的数据,提交就AC了。

 

#include<cstdio>#include<iostream>#include<list>#include<string>using namespace std;list<int> l[25],temp;int point[25];void remove_(int x){    int i = point[x];    while(l[i].back() != x)    {        int t = l[i].back();        l[t].push_back(t);        point[t] = t;        l[i].pop_back();    }}void move_(int x,int y){    int i = point[x], j = point[y];    while(l[i].back() != x)    {        temp.push_back(l[i].back());        l[i].pop_back();    }    l[j].push_back(l[i].back());    point[x] = j;    l[i].pop_back();    while(!temp.empty())    {        l[j].push_back(temp.back());        point[temp.back()] = j;        temp.pop_back();    }}int main(){    int n;    cin >> n;    for(int i = 0;i < n;i++)    {        l[i].push_back(i);        point[i] = i;    }    string str1,str2;    int a,b;    while(cin >> str1 && str1 != "quit" )    {        cin >> a >> str2 >> b;        if(str1 == "move" && str2 == "onto")        {            remove_(a);            remove_(b);            move_(a,b);        }        else if(str1 == "move" && str2 == "over")        {            remove_(a);            move_(a,b);        }        else if(str1 == "pile" && str2 == "onto")        {            remove_(b);            move_(a,b);        }        else        {            move_(a,b);        }    }    for(int i = 0;i < n;i++)    {        cout << i << :;        while(!l[i].empty())        {            cout << " " << l[i].front();            l[i].pop_front();        }        cout << endl;    }    return 0;}

 

  

POJ_1208_模拟