The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on their own table (numbered from 0 to n-1, means book 0 lies on table 0) with book bi adjacent to book bi+1 for all 0 <= i < n-1
as shown in the diagram below:
|
Book 0 |
Book 1 |
Book 2 |
Book 3 |
Book 4 |
Book 5 |
…… |
Book N-1 |
|
Table 0 |
Table 1 |
Table 2 |
Table 3 |
Table 4 |
Table 5 |
Table N-1 |
The valid commands and limited for moving books are:
Any command in which A = B or in which A and B are in the same stack of books is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of books.
1. pile A onto B
Return any books that are stacked on the top of book B to their own table.
Then puts book A and all books on the top of book A onto the top of book B.
2. exit
Finish moving the books
Hint: you can use following code.
version 1:
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node{
struct _Node* next;
int val;
} Node;
Node* table[25];
int pos[25];
void resetBook(int p2) {
// TODO 1
}
void pileOnto(int p1, int p2) {
// TODO 2
}
void initialize(int n) {
for(int i = 0; i<n; i++){
table[i] = (Node*)malloc(sizeof(Node));
table[i]->val = -1;
table[i]->next = (Node*)malloc(sizeof(Node));
table[i]->next->val = i;
pos[i] = i;
table[i]->next->next = NULL;
}
}
int main() {
int n;
scanf("%d", &n);
initialize(n);
while(1){
char input[100] = {0};
int p1, p2; scanf("%s", input);
if(input[0] == 'e') break;
scanf("%d%s%d", &p1, input, &p2);
if(pos[p1] == pos[p2]) continue;
resetBook(p2);
pileOnto(p1, p2);
}
Node* tmp;
for(int i = 0; i < n; i++){
printf("%d:", i);
tmp = table[i]->next;
while(tmp){
printf(" %d", tmp->val);
tmp = tmp->next;
}
printf("\n");
}
return 0;
}
version 2:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node{
int data;
int table;
struct node *next;
}Node;
Node* nodes[10000];
void clean(int b){
// TODO 1
}
void mymove(int a, int b){
// TODO 2
}
Node* createNode(int data){
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
node->table = data;
return node;
}
void print(int n){
for (int i = 0; i < n ; i++){
printf("%d:", i);
Node *p = nodes[i];
if (p->table == i){
while(p!= NULL){
printf(" %d", p->data);
p = p->next;
}
}
printf("%c",'\n');
}
}
int main()
{
int n;
char op1[5], op2[5];
int a, b;
scanf("%d", &n);
for (int i = 0; i < n ; i++){
nodes[i] = createNode(i);
}
while(scanf("%s", op1) && op1[0] != 'e'){
scanf("%d %s %d", &a, op2, &b);
if (a == b || nodes[a]->table == nodes[b]->table) continue;
// op1 == "pile", op2 == "onto"
clean(b);
mymove(a, b);
}
print(n);
return 0;
}
The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n < 25.
The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
The output should consist of the final state of the books. Each table numbered i (0 <= i < n, where n is the number equal to books initial position) should appear followed immediately by a colon.
If there is at least a book on it, the colon must be followed by one space, followed by a list of books that appear stacked in that position with each book number separated from other book numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each book position (i.e., n lines of output where n is the integer on the first line of input).
You are asked to add a new line character at the end.