2008年10月30日 星期四

ACM101 The Blocks Problem 


#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class Q101
{
      public:
              map > thelist;
              int _size;
              void SetSize(int size)
              {
                   _size=size;
                   for(int i=0;i<_size;++i)
                   {
                       thelist[i].clear();
                       thelist[i].push_back(i);
                   }
               }
              
              void Show()
              {
                   for(int i=0;i<_size;++i)
                   {
                           cout << i << ":";
                          
                           for(list::iterator iter=thelist[i].begin();iter!=thelist[i].end();++iter)
                           {
                               cout << " " << *iter;
                           }
                           cout << endl;
                   }
               }
               
               int Search(int n)
               {
                    for(map>::iterator iter=thelist.begin();iter!=thelist.end();++iter)
                    {
                        for(list::iterator iter2=iter->second.begin();iter2!=iter->second.end();++iter2)
                        {
                            if(*iter2==n)
                            {
                                return iter->first;
                            }
                        }
                    }
                    return -1;
                    
                }
                
               void ResetAfter(int n)
               {
                    int index=Search(n);
                    while(thelist[index].back()!=n)
                    {
                       int temp=thelist[index].back();
                       thelist[index].pop_back();
                       thelist[temp].push_back(temp);
                    }
                }
                
                stack GetStack(int n)
                {
                    stack s;
                    int index =Search(n);
                    while(thelist[index].back()!=n)
                    {
                        s.push(thelist[index].back());
                        thelist[index].pop_back();
                    }
                    s.push(thelist[index].back());
                    thelist[index].pop_back();
                    return s;
                }
               void moveonto(int a,int b)
               {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(a);
                   ResetAfter(b);
                  
                   thelist[aat].pop_back();
                   thelist[bat].push_back(a);
                }
               void moveover(int a,int b)
               {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(a);            
                   thelist[aat].remove(a);
                   thelist[bat].push_back(a);
                }
                void pileonto(int a,int b)
                {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                   ResetAfter(b);
                   stack s=GetStack(a);
                   while(!s.empty())
                   {
                       thelist[bat].push_back(s.top());
                       s.pop();
                   }
                }
                 void pileover(int a,int b)
                {
                   if(a==b)
                   {
                           return;
                   }
                   int aat= Search(a);
                   int bat=Search(b);
                   if(aat==bat)
                   {
                      return;
                   }
                
                   stack s=GetStack(a);
                   while(!s.empty())
                   {
                       thelist[bat].push_back(s.top());
                       s.pop();
                   }
                }
};
int main(int argc, char *argv[])
{
    Q101 q101;
    while(true)
    {
       int size;
       cin >> size;
       if(cin.eof())
       {
           break;
       }
       q101.SetSize(size);
       
       while(true)
       {
        string cmd1,cmd2;
        int a,b;
        string input;
        getline(cin,input);
        istringstream ss;
        ss.str(input);
        ss >> cmd1;
       
         if(cmd1=="quit")
        {
            q101.Show();            
            break;
        }
        ss >> a;
        ss >> cmd2;
        ss >> b;
        if(cmd1=="move")
        {
           if(cmd2=="onto")
           {
               q101.moveonto(a,b);
           }
           else if(cmd2=="over")
           {
                q101.moveover(a,b);
           }
        }
        else if(cmd1=="pile")
        {
        if(cmd2=="onto")
           {
               q101.pileonto(a,b);
           }
           else if(cmd2=="over")
           {
                q101.pileover(a,b);
           }
        }   
       }       
    }
}
張貼者： yup 於 晚上11:50
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)