ACM-101 The Blocks Problem with C++

經過了3天的激戰

順利的擊敗了ACM-101

執行時間0.020 排名2901

神人好多阿

#include <sstream>
#include <iostream>
#include <stdio.h>
#include <ctype.h>
#include <cstdio>
#include <list>

using namespace std;

list <int> block[25];  // 25 stack
int pos[25];  // if block 1 is in the stack and the base block is 5 then pos[1] = 5;


void initiate();
void printresult(int x);
void moveonto(int a , int b);
void moveover(int a , int b);
void pileonto(int a , int b);
void pileover(int a , int b);
bool checkblock(int a , int b);


int main(int argc, char* argv[])
{
 int block_1, block_2;
 int final;


 string str1, str2;
 string quit = "quit";
 string move = "move";
 string pile = "pile"; 
 string onto = "onto"; 
 string over = "over"; 
 
 while( cin>>str1 )
 {
  if(str1 == quit)//print the final result
  {
   printresult(final);                  
  }else if(str1 == move || str1 == pile) // move and pile action
  {
   cin >> block_1 >> str2 >> block_2;
   if(block_1 != block_2 && checkblock(block_1 , block_2))
   {
    if(str1 == move)
    {
     if(str2 == onto)
     {
      moveonto(block_1 , block_2);
     }else
     {
      moveover(block_1 , block_2);
     }
    }else
    {
     if(str2 == onto)
     {
      pileonto(block_1 , block_2);
     }else
     {
      pileover(block_1 , block_2);
     }
    }           
   }else
   {
    //cout<<"Are you kidding"<<endl;
   }               
  }else  // how many blocks are used in the process
  {
   istringstream stream1;
   stream1.str(str1);
   stream1 >> final;
   initiate();
  }
 }
 return 0;
}


void initiate()
{
 for(int i=0 ; i<25 ; i++)
 {
  if(block[i].empty())
  {
   block[i].push_back(i);
   pos[i] = i;
  }else
  {
   block[i].clear();
   block[i].push_back(i);
   pos[i] = i;
  }
 }
}


void printresult(int x)
{
 list<int>::iterator iter2;
 for(int y=0 ; y<x ; y++)
 {
  iter2 = block[y].begin();
  cout << y <<":";
  while( iter2 != block[y].end() ) 
  {
   cout <<" "<<*iter2;
   ++iter2;
  } 
  cout<<endl;
 }
}


bool checkblock(int a , int b)
{
 if(pos[a] != pos[b])
 return true;
 else
 return false;     
}



void moveonto(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos1, bpos2;                  
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 while(bpos1 != a)  //put the last block back 
 {
  block[bpos1].push_back(bpos1);
  pos[bpos1] = bpos1;
  block[temp_pos1].pop_back();
  bpos1 = block[temp_pos1].back();
 }
 
 while(bpos2 != b)  //put the last block back
 {
  block[bpos2].push_back(bpos2);
  pos[bpos2] = bpos2;
  block[temp_pos2].pop_back();
  bpos2 = block[temp_pos2].back();
 }
 
 /*** move the first block onto the second block ***/          
 block[temp_pos1].pop_back();     
 block[temp_pos2].push_back(a);
 pos[a] = temp_pos2;
}

void moveover(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos1;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
      
 while(bpos1 != a)  //put the last block back 
 {
  block[bpos1].push_back(bpos1);
  pos[bpos1] = bpos1;
  block[temp_pos1].pop_back();
  bpos1 = block[temp_pos1].back();
 }
 
 /*** move the first block onto the second block ***/          
 block[temp_pos1].pop_back();     
 block[temp_pos2].push_back(a);
 pos[a] = temp_pos2;
}

void pileonto(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 int bpos2;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 list<int> mylist;
 list<int>::iterator it;
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 //bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 for(it=block[temp_pos1].begin() ; it!=block[temp_pos1].end() ; it++)
 {
  if(*it == a)
  {
   mylist.splice ( mylist.begin(), block[temp_pos1], it, block[temp_pos1].end());
   break;
  }
 }
 
 
 while(bpos2 != b)  //put the last block back
 {
  block[bpos2].push_back(bpos2);
  pos[bpos2] = bpos2;
  block[temp_pos2].pop_back();
  bpos2 = block[temp_pos2].back();
  //cout<<"*";
 }
 
 
 block[temp_pos2].splice(block[temp_pos2].end(),mylist);
 for(it=block[temp_pos2].begin() ; it!=block[temp_pos2].end() ; it++)
      {
  pos[*it] = temp_pos2;
 }
 pos[a] = temp_pos2;
}

void pileover(int a , int b)
{
 int temp_pos1, temp_pos2;
 //use to present the target block's position; 
 //if the target block is "3" and the stack is "1 2 3" ; then temp_pos = 1
 
 //int bpos1, bpos2;
 //use to present the last block in the stack; 
 //if the stack is "1 2 3" then bpos = 3
 
 list<int> mylist;
 list<int>::iterator it;
 
 /*** put the block back ***/     
 temp_pos1 = pos[a];                //where is the block a 
 //bpos1 = block[temp_pos1].back();   //the last block in the stack a
 
 temp_pos2 = pos[b];                //where is the block b
 //bpos2 = block[temp_pos2].back();   //the last block in the stack b
 
 for(it=block[temp_pos1].begin() ; it!=block[temp_pos1].end() ; it++)
 {
  if(*it == a)
  {
   mylist.splice ( mylist.begin(), block[temp_pos1], it, block[temp_pos1].end());
   break;
  }
 }
 
 block[temp_pos2].splice(block[temp_pos2].end(),mylist);
 for(it=block[temp_pos2].begin() ; it!=block[temp_pos2].end() ; it++)
 {
  pos[*it] = temp_pos2;
 }
 pos[a] = temp_pos2;
}