I'm writing a program to solve this problem:
Stock stored containers with goods of various kinds of N . All containers are written in N stacks . In each stack may be containers with goods of any species ( stack can be initially empty) .
Forklift can take any of the top container pile and put it on top of any stack . You must put all the containers with the product of the first kind in the first stack , the second type - the second stack , etc.
The program should print the sequence of actions forklift or a message stating that the problem has no solution .
Input Format
The first line of input contains a single positive integer N, does not exceed 500 . The next N lines describe the stack of containers , first recorded by ki - number of containers in the stack , and then ki properties - types of goods in containers in the stack from the bottom up . At the beginning of each stack of not more than 500 containers ( containers during transport this restriction can be broken ) . Output data format The program should print the description of the truck action : for each action type two numbers - from which to take the container stacks and stack which put. ( Note that minimize the amount of truck operations is not required. ) If there is no solution , you need to display a single number 0 . If the containers are initially correctly placed into piles , the output does not need anything .
Example:
Input:
3
4 1 2 3 2
0
0
Output:
1 2
1 3
1 2
So, I wrote a program. And you can see the code below:
#include <iostream>
using namespace std;
// Здесь, короче, стек.
struct Node{
int data;
Node *next;
};
Node* push(Node *start, int d){
Node *a = new Node;
a -> data = d;
a -> next = start;
return a;
}
Node* pop(Node *s, int &d){
d = (s -> data);
Node *a = s -> next;
delete s;
return a;
}
void move(Node **stack, int from, int to, int save, int *size, int *number){
int k = 0;
while(size[to] != number[to]){
stack[from] = pop(stack[from], k);
if(k - 1 == to){
stack[to] = push(stack[to], k);
size[to]++;
cout << from + 1 << " " << to + 1 << endl;
}
else{
stack[save] = push(stack[save], k);
size[save]++;
cout << from + 1 << " " << save + 1 << endl;
}
size[from]--;
}
if(save > to){
while(size[save] != number[save]){
stack[save] = pop(stack[save], k);
stack[from] = push(stack[from], k);
size[save]--;
size[from]++;
cout << save + 1 << " " << from + 1 << endl;
}
}
else{
while(size[save] != 0){
stack[save] = pop(stack[save], k);
stack[from] = push(stack[from], k);
size[save]--;
size[from]++;
cout << save + 1 << " " << from + 1 << endl;
}
}
}
void to_one(Node **stack, int to, int m, int *size){
int k = 0;
for(int i = to + 1; i < m; i++){
while(size[i] != 0){
stack[i] = pop(stack[i], k);
stack[to] = push(stack[i], k);
size[to]++;
size[i]--;
cout << i + 1 << " " << to + 1 << endl;
}
}
}
int main(){
int n = 0;
int k = 0;
cin >> n;
Node **stack = new Node*[n]; // наши полки
int *size = new int[n]; // количество элементов на каждой полке изначально
int *number = new int[n]; // количество элементов соответствующего типа
for(int i = 0; i < n; i++) number[i] = 0;
for(int i = 0; i < n; i++){
cin >> size[i];
for(int j = 0; j < size[i]; j++){
cin >> k;
number[k - 1]++;
stack[i] = push(stack[i], k);
} // формируем наши полки
}
int from = 0;
int m = n; // вспомогательная переменная количества неотсортированных полок
//сперва все перенесем в одну полку (первую)
to_one(stack, from, m, size);
int save = 1; // вспомогательная
//Теперь восстановим последнюю стопку, а вспомогательной будет вторая.
int to = m - 1;
move(stack, from, to, save, size, number);
//Теперь наша готовая последняя стопка станет резервной навсегда.
save = to;
//А теперь отдельно рассмотрим полки между последней и первой, повторив цикл выше.
m--;
for(int i = m; i > from; i--){
to = i - 1;
to_one(stack, from, i, size);
move(stack, from, to, save, size, number);
}
delete []number;
delete []size;
return 0;
}
I tried to debug it and this is what I got. My input was:
4
4 1 2 3 4
1 3
3 2 1 4
3 2 1
Program crashed after this output:
2 1
3 1
3 1
3 1
4 1
4 1
1 2
Screenshot:
I don't know why I get this error. Help me please.
Problem was in
stack[to] = push(stack[i], k);
Should be
stack[to] = push(stack[to], k);
Thanks to Joe Z.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments