The blocks problem (uva101) Purple Book p110vector application

Purple Book P110;vector Application ;UVa101 The Blocks Problem

Vjudge Please move the title address here

The main idea of the topic ：

Input n (0<n<25), Get the number 0 To n-1 Wooden block , They are placed in order and numbered 0 To n-1 The location of . Now operate these wooden blocks , There are four types of operations .

• move a onto b： Put a piece of wood a、b Put the wooden blocks on the back to their original positions , And then a Put it in b On ;
• move a over b： hold a Put the wooden blocks on the back to their original positions , And then a Send to include b On the pile of ;
• pile a onto b： hold b Put the wooden blocks on the back to their original positions , And then a together with a Move the wooden block on to b On ;
• pile a over b： hold a together with a The upper wood block is moved to include b On the pile of .

When the input quit when , End the operation and output 0~n-1 The position of the wooden block .

Sample Input
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Sample Output
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

Topic analysis （ The idea is based on the purple book ）：

data structure choice ： Within each cell block The number of is dynamic , Solid can be used vector Simulate a cell , The cells have a total of n individual ,n Values determine , So you can open one. Each unit is vector Array of ：vector<int> pile[26]

Algorithm design ： The topic involves the movement of whole data and single data , And n The biggest only 25, The time complexity of the simulation method is sufficient .
The simulation process involves two steps ：<1. Restore block <2. Move block;
Analyze the four instructions in the topic ：
move Need to put a upper block All restored , Move alone a;
pile There is no need to restore a upper block, The whole section needs to be moved ;
onto Need to put b upper block All restored , requirement a And b adjacent ;
over No need to restore b upper block, Move again a Or the whole section .
Analyze the similarities and differences of the four instructions and combine the sequence of first recovery and then movement , Teacher liurujia skillfully handled the following ( Some places are different from the original code )：

//pa and pb by a and b Array subscript of ,ha and hb by a and b Of vector Subscript 
if(order1=="move") clear_above(pa,ha);// take pa,ha Above the position block Restore 
if(order2=="onto") clera_above(pb,hb);// take pb,hb Above the position block Restore 
pile_onto(pa,ha,pb);// take pa,ha Position and above block Move to pb Apex 

Module design ： thus , The basic framework of the program is ： Preprocessing – Input and initialization – simulation – Output –return 0;.

Code ：

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int n,a,b;
string order1,order2;
vector<int> pile[26];

void find_block(int num,int& h,int& p);
void clear_above(int h,int p);
void pile_onto(int p1,int h1,int p2);
void print();

int main()
{
    
	 // Read in and initialize  
	 scanf("%d",&n);
	 for(int i=0;i<n;i++) pile[i].push_back(i);
	 // simulation  
	 while(cin>>order1>>a>>order2>>b)
	 {
    
	 	 int ha,hb,pa,pb;
	 	 find_block(a,ha,pa);
	 	 find_block(b,hb,pb);
	 	 if(pa==pb) continue;
	 	 if(order1=="move") clear_above(ha,pa);
	 	 if(order2=="onto") clear_above(hb,pb);
	 	 pile_onto(pa,ha,pb);
	 	 //print();
	 }
	 // Output 
	 print();
	 return 0;
}

void find_block(int num,int& h,int& p)
{
    
	 for(p=0;p<n;p++)
	 	 for(h=0;h<pile[p].size();h++)
	 	 	 if(pile[p][h]==num) return ;
}

void clear_above(int h,int p)
{
    
	 for(int i=h+1;i<pile[p].size();i++)
	 	 pile[pile[p][i]].push_back(pile[p][i]);
	 pile[p].resize(h+1);
	 return ;
}

void pile_onto(int p1,int h1,int p2)
{
    
	 for(int i=h1;i<pile[p1].size();i++)
	 	 pile[p2].push_back(pile[p1][i]);
	 pile[p1].resize(h1);
	 return ;
}

void print()
{
    
	 for(int i1=0;i1<n;i1++)
	 {
    
	 	 printf("%d:",i1);
	 	 for(int i2=0;i2<pile[i1].size();i2++) printf(" %d",pile[i1][i2]);
	 	 printf("\n");
	 }
}

Summary of key points and details ：

1. Teacher liurujia is calculating a Block and b Where the block is h And p when , Adopted Pass value by reference Methods , A function computes two local variables at the same time ：

void find_block(int num,int& h,int& p)

2. The choice of data structure vector Array , The functions used in the topic are v.size();v.resize();v.push_back();
3. Extract the common ground of the four instructions , Design two functions to reduce repeated code .

Updated on 2020.6.22