101 - The Blocks Problem

[Maciej]

I have got runtime error 101, what is wrong?
On my PC everything is ok.
[cpp]

/* @JUDGE_ID: XXXXXX 101 C++ "" */
#include <stdio.h>
#include <string.h>

struct node
{
node* next; int item;
node(int x = 0) { item = x; next = 0; }
};
typedef node* link;

void move_onto(link a, link b)
{
link t = a->next;
a->next = a->next->next;
link k = b->next->next;
b->next->next = t;
t->next = k;
}
void move_over(link a, link b)
{
link t = b->next;
while(t->next != 0)
t = t->next;
link k = a->next;
a->next=a->next->next;
t->next = k;
k->next = 0;
}
void pile_onto(link a, link b)
{
link t = a->next;
a->next = 0;
link k = b->next->next;
b->next->next = t;
while(t->next != 0)
t = t->next;
t->next = k;
}
void pile_over(link a, link b)
{
link t = b->next;
while(t->next != 0)
t = t->next;
t->next = a->next;
a->next = 0;
}


int main()
{
int max, a, b, i, j;
scanf("%d", &max);
if(max<0 || max>25) return 0;
char txt1[100], txt2[100];
link tab = new node[max];

for(int i = 0; i<max; i++)
tab.next = new node(i);


while(1)
{
scanf("%s", txt1);
if(strcmp(txt1, "quit")==0) break;

scanf("%d %s %d", &a, txt2, &b);

if(a<0 || a>=max || b<0 || b>=max) continue;

link ta, tb;
for(i = 0; i<max; i++)
{ ta = &tab;
while(ta->next != 0)
{
if(ta->next->item == a) break;
ta=ta->next;
}
if(ta->next->item == a) break;
}
for(j = 0; j<max; j++)
{ tb = &tab[j];
while(tb->next != 0)
{
if(tb->next->item == b) break;
tb=tb->next;
}
if(tb->next->item == b) break;
}
if(a == b) continue;
if(i == j) continue;

if(strcmp(txt1, "move") == 0)
if(strcmp(txt2, "onto") == 0) move_onto(ta, tb);
else move_over(ta, tb);
else
if(strcmp(txt2, "onto") == 0) pile_onto(ta, tb);
else pile_over(ta, tb);

}

for(int o = 0; o < max; o++)
{
link t = tab[o].next;
printf("%d: ", o);
while(t != 0)
{ printf("%d ", t->item); t=t->next; }
printf("\n");
}
return 0;
}
//@end_of_source_code[/cpp]

[rdinix]

First of all, format your program like this:

[cpp]while
{
command 1;
command 2;
etc...;
}[/cpp]

Second, put /* COMMENTS */

Third, put a routine that prints the 25x25 matrix after every input, so you can check what

[dev_mania]

I got Time Limit Exceeded Message....
How can I make my program faster.....?????

Code: Select all

/*   @BEGIN_OF_SOURCE_CODE         */
/*   @JUDGE_ID: XXXXX  101     C    */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char   UINT8;

typedef struct _node{
        UINT8 bkNumber;
        UINT8 lstNumber;
        struct _node* next;
}NODE;

typedef struct _list{
        struct _node* head;
}LIST;

typedef struct _listControl{
        UINT8 listCount;
        struct _list* list;
}LISTCONTROL;

void initialize(LISTCONTROL* listControl, UINT8 count);
void destroy(LISTCONTROL* listControl);
NODE* searchNode(LISTCONTROL* listControl, UINT8 stdNumber, NODE** prev);
void returnInitPos(LISTCONTROL* listControl, NODE* currentNode);
void appendNode(LISTCONTROL* listControl, NODE* node, NODE* destin, UINT8 option);
void moveOnto(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum);
void moveOver(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum);
void pileOnto(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum);
void pileOver(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum);  
void printList(LISTCONTROL* listControl);   
void parsing(char* inputLine, char* cmd1, char* cmd2, UINT8* origin, UINT8* destin);

int main(){
        LISTCONTROL listControl;
        UINT8 listCount;
        UINT8 command;
        char cmd1[5];
        char cmd2[5];
        char inputLine[20];
        UINT8 origin, destin;               
        
        scanf("%u", &listCount);        
        initialize(&listControl, listCount);         
        getc(stdin);
                
        while(gets(inputLine) != NULL){
                command = 0;                                                              
                                
                parsing(inputLine, cmd1, cmd2, &origin, &destin);                                          
                
                if(strcmp(cmd1, "quit") == 0){
                        break;
                }
                else if(strcmp(cmd1, "move") == 0 && strcmp(cmd2, "onto") == 0){
                        command = 1;
                }
                else if(strcmp(cmd1, "move") == 0 && strcmp(cmd2, "over") == 0){ 
                        command = 2;
                }
                else if(strcmp(cmd1, "pile") == 0 && strcmp(cmd2, "onto") == 0){
                        command = 3;
                }
                else if(strcmp(cmd1, "pile") == 0 && strcmp(cmd2, "over") == 0){ 
                        command = 4;
                }           
                
                switch(command){
                case 1:
                        moveOnto(&listControl, origin, destin);
                        break;
                case 2:
                        moveOver(&listControl, origin, destin);
                        break;
                case 3:
                        pileOnto(&listControl, origin, destin);
                        break;
                case 4:
                        pileOver(&listControl, origin, destin);
                        break;                                                 
                }                       
        }      
        
        printList(&listControl);      
        destroy(&listControl);
        
        return 0;
}

void parsing(char* inputLine, char* cmd1, char* cmd2, UINT8* origin, UINT8* destin){
        int i;
        
        for(i = 0; i < 4; i++){
                cmd1[i] = inputLine[i];
        }
        cmd1[4] = '\0';       
        
        *origin = atoi(&inputLine[5]);
                
        for(i = 0; i < 4; i++){
                cmd2[i] = inputLine[i + 7];                
        }
        cmd2[4] = '\0';
        
        *destin = atoi(&inputLine[12]);
        
        return;
}            

void initialize(LISTCONTROL* listControl, UINT8 count){
        NODE* nNode;
        int i;        
        
        listControl->listCount = count;        
        listControl->list = (LIST*)malloc(sizeof(LIST) * count);
        
        for(i = 0; i < count; i++){
                nNode = (NODE*)malloc(sizeof(NODE) * 1);
                
                nNode->bkNumber = i;
                nNode->lstNumber = i;
                nNode->next = NULL;
                               
                listControl->list[i].head = nNode;
        }
                
        return;
}

void destroy(LISTCONTROL* listControl){
        NODE* current;
        NODE* temp;
        int i;
        
        for(i = 0; i < listControl->listCount; i++){
                current = listControl->list[i].head;
                
                if(current == NULL) continue;                
                
                while(current != NULL){
                        temp = current->next;                        
                        free(current);
                        current = temp;
                }
        }
        
        free(listControl->list);
        
        return;
}          

NODE* searchNode(LISTCONTROL* listControl, UINT8 stdNumber, NODE** prev){        
        NODE* currentNode;
        NODE* retVal = NULL;        
        int i;             
        
        for(i = 0; i < listControl->listCount; i++){
                currentNode = listControl->list[i].head;               
                
                *prev = NULL;
                
                while(currentNode != NULL){
                        if(currentNode->bkNumber == stdNumber){                                                            
                                retVal = currentNode;                         
                                goto EXIT;                        
                        }                         
                        
                        *prev = currentNode;                 
                        currentNode = currentNode->next;
                }
        }
                
EXIT:        
        return retVal;
}        

void returnInitPos(LISTCONTROL* listControl, NODE* startNode){                
        
        while(startNode != NULL){
                listControl->list[startNode->bkNumber].head = startNode;
                startNode->lstNumber = startNode->bkNumber;
                
                startNode = startNode->next;
        }
        
        return;
}

void appendNode(LISTCONTROL* listControl, NODE* node, NODE* destin, UINT8 option){         
        while(destin->next != NULL){
                destin = destin->next;
        }
        
        if(option == 1) node->next = NULL;        
        
        node->lstNumber = destin->lstNumber;                        
        destin->next = node;       
                        
        return;
}

void moveOnto(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum){
        NODE* origin;
        NODE* destin;
        NODE *prevO, *prevD;
        
        origin = searchNode(listControl, originNum, &prevO);       
        destin = searchNode(listControl, destinNum, &prevD);   
        
        if(origin->lstNumber == destin->lstNumber) return;    
                
        returnInitPos(listControl, origin->next);
        returnInitPos(listControl, destin->next);
        
        origin->next = NULL;
        destin->next = NULL;
        
        appendNode(listControl, origin, destin, 1);                
        
        if(prevO == NULL){
                listControl->list[origin->bkNumber].head = NULL;
        }
        else{                        
                prevO->next = NULL;       
        }                
        
        return;
}

void moveOver(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum){
        NODE* origin;
        NODE* destin;
        NODE *prevO, *prevD;
        
        origin = searchNode(listControl, originNum, &prevO);
        destin = searchNode(listControl, destinNum, &prevD);
        
        if(origin->lstNumber == destin->lstNumber) return;    
        
        returnInitPos(listControl, origin->next);
        origin->next = NULL;
        
        appendNode(listControl, origin, destin, 1);
        
        if(prevO == NULL){
                listControl->list[origin->bkNumber].head = NULL;
        }
        else{
                prevO->next = NULL;
        }                
        
        return;
}
 
void pileOnto(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum){
        NODE* origin;
        NODE* destin;
        NODE *prevO, *prevD;
        
        origin = searchNode(listControl, originNum, &prevO);
        destin = searchNode(listControl, destinNum, &prevD);
        
        if(origin->lstNumber == destin->lstNumber) return;    
        
        returnInitPos(listControl, destin->next);
        destin->next = NULL;
        
        appendNode(listControl, origin, destin, 2);
        
        if(prevO == NULL){
                listControl->list[origin->bkNumber].head = NULL;
        }
        else{                                
                prevO->next = NULL;
        }                
        
        return;
}

void pileOver(LISTCONTROL* listControl, UINT8 originNum, UINT8 destinNum){
        NODE* origin;
        NODE* destin;
        NODE *prevO, *prevD;
        
        origin = searchNode(listControl, originNum, &prevO);
        destin = searchNode(listControl, destinNum, &prevD); 
        
        if(origin->lstNumber == destin->lstNumber) return;          
        
        appendNode(listControl, origin, destin, 2);
        
        if(prevO == NULL){
                listControl->list[origin->bkNumber].head = NULL;
        }
        else{                        
                prevO->next = NULL;        
        }                
        
        return;
}

void printList(LISTCONTROL* listControl){
        NODE* current;
        int i;       
        
        for(i = 0; i < listControl->listCount; i++){
                printf("\n%u: ", i);
                
                current = listControl->list[i].head;
                
                while(current != NULL){                        
                        printf("%u ", current->bkNumber);
                        
                        current = current->next;
                }
        }
        printf("\n");
        
        return;
}

/*   @END_OF_SOURCE_CODE         */   

[Balon]

you got wrong mean of the problem!!
when
0: 0 1 2 3
1:
2:
3:
4: 4 5 6
5:
6:

move 4 onto 1 results:
0: 0 1 4
1: 1
2: 2
3: 3
4:
5: 5
6: 6

while move 4 over 1 results:
0: 0 1 2 3 4
1:
2:
3:
4:
5: 5
6: 6

while pile 4 onto 1 results:
0: 0 1 4 5 6
1:
2: 2
3: 3
4:
5:
6:

while pile 4 over 1 results:
0: 0 1 2 3 4 5 6
1:
2:
3:
4:
5:
6:

read the problem more carefully

BTW. use array is safer than use list maintained by yourself when the data limit is so small ( 0<n<25 )

[Lee Seung-chul]

I think that this source is right. But I got WA from online-judge. --;;
[c]
/* @JUDGE_ID: 25429XW 101 C */
#include <stdio.h>
#include <string.h>
#define EMPTY -1
#define SIZE 30

int n;
int blocks[SIZE][SIZE];
int a_i, a_j, b_i, b_j;

void go_init(char);
void MoveOnto(int, int);
void MoveOver(int, int);
void PileOnto(int, int);
void PileOver(int, int);
void GetPos(char, int);
void ResultPrint();

int main()
{
int i,j;
char cmd1[5], cmd2[5], a, b;

for(i=0; i<SIZE; i++)
{
blocks[0]=i;
for(j=1; j<SIZE; j++) blocks[j] = EMPTY;
}

scanf("%d", &n);

while(1)
{
scanf("%s", cmd1);
if(!strcmp(cmd1, "quit")) break;
scanf("%d %s %d", &a, cmd2, &b);

GetPos('a', a);
GetPos('b', b);

if(a!=b && a_i!=b_i)
{
GetPos('a', a);
GetPos('b', b);
if(!strcmp(cmd1, "move"))
{
if(!strcmp(cmd2, "onto")) MoveOnto(a, b);
if(!strcmp(cmd2, "over")) MoveOver(a, b);
}
if(!strcmp(cmd1, "pile"))
{
if(!strcmp(cmd2, "onto")) PileOnto(a, b);
if(!strcmp(cmd2, "over")) PileOver(a, b);
}
}
}
ResultPrint();
return(0);
}

void go_init(char ab)
{
int i;

if(ab='a')
for(i=a_j+1; blocks[a_i]!=EMPTY; i++)
{
blocks[blocks[a_i]][0] = blocks[a_i];
blocks[a_i] = EMPTY;
}
else
for(i=b_j+1; blocks[b_i]!=EMPTY; i++)
{
blocks[blocks[b_i]][0] = blocks[b_i];
blocks[b_i] = EMPTY;
}
}
void MoveOnto(int a, int b)
{
go_init('a');
go_init('b');

blocks[a_i][a_j]=EMPTY;
blocks[b_i][b_j+1]=a;
}

void MoveOver(int a, int b)
{
int i;

go_init('a');

blocks[a_i][a_j]=EMPTY;
i=0;
while(blocks[b_i][i]!=EMPTY) i++;

blocks[b_i][i]=a;
}

void PileOnto(int a, int b)
{
int i;

go_init('b');

for(i=a_j; blocks[a_i][i]!=EMPTY; i++)
{
blocks[b_i][b_j + i - a_j + 1] = blocks[a_i][i];
blocks[a_i][i]=EMPTY;
}

}

void PileOver(int a, int b)
{
int i, j=0;

while(blocks[b_i][j]!=EMPTY) j++;

for(i=a_j; blocks[a_i][i]!=EMPTY; i++)
{
blocks[b_i][j + i - a_j] = blocks[a_i][i];
blocks[a_i][i]=EMPTY;
}
}

void GetPos(char flag, int block)
{
int i, j;

for(i=0; i<n; i++)
for(j=0; j<n && blocks[i][j]!=EMPTY; j++)
if(blocks[i][j]==block)
{
if(flag=='a')
{
a_i = i;
a_j = j;
}
else
{
b_i = i;
b_j = j;
}
return;
}
}

void ResultPrint()
{
int i, j;
for(i=0; i<n; i++)
{
printf("%d:", i);
for(j=0; blocks[i][j]!=EMPTY; j++)
printf(" %d", blocks[i][j]);
printf("\n");
}
}
[/c]

[Moni]

Ok!
I need the exec. You can send that to me.

[james-b]

I've confirmed my program for million times,but it still responds me WA...

[c]
#include<stdio.h>
#include<string.h>

int num[24][24];

/*num[Y][X] ,Y=across X=straight*/

void throw(int);

int find_y(int a)
{
int i,j;
for(i=0;i<24;i++)
{
for(j=0;j<24;j++)
{
if(num[j]==a)
return i;

}
}
}
/*find the position of Across*/

int find_x(int a)
{
int i,j;
for(i=0;i<24;i++)
{
for(j=0;j<24;j++)
{
if(num[j]==a)
return j;
}
}
}
/*find the position of Straight*/

void mov_onto(int a,int b)
{
if(find_x(a)!=find_x(b))
{
int i,j,k,l;
i=find_y(b)+1;
j=find_x(b);
k=find_y(a)+1;
l=find_x(a);
throw(num[j]);
throw(num[k][l]);
num[j]=a;
num[find_y(a)][l]=-1;
}
else;
}

void mov_over(int a,int b)
{
if(find_x(a)!=find_x(b))
{
int i,j,k,l;
i=find_y(b);
j=find_x(b);
k=find_y(a)+1;
l=find_x(a);
throw(num[k][l]);
while(num[j]!=-1)
i++;
num[j]=num[find_y(a)][l];
num[find_y(a)][l]=-1;
}
else;
}

void pil_onto(int a,int b)
{
int i,j,k,l;
i=find_y(b)+1;
j=find_x(b);
k=find_y(a);
l=find_x(a);
if(l!=j)
{
throw(num[j]);
while(num[k][l]!=-1)
{
num[j]=num[k][l];
num[k][l]=-1;
i++;
k++;
}
}
else;
}


void pil_over(int a,int b)
{
int i,j,k,l;
i=find_y(b)+1;
j=find_x(b);
k=find_y(a);
l=find_x(a);
if(l!=j)
{
while(num[j]!=-1)
i++;
while(num[k][l]!=-1)
{
num[j]=num[k][l];
num[k][l]=-1;
i++;
k++;
}
}
}

void throw(int a)
{
int i,j,k;
i=find_y(a);
j=find_x(a);
while(num[i][j]!=-1)
{
for(k=0;k<24;k++)
{
if(num[i][j]==k)
{
num[0][k]=k;
num[i][j]=-1;
break;
}
}
i++;
}
}

void out(int a)
{
int i,j;
for(i=0;i<a;i++)
{
if(i<10)
printf(" %d:",i);
else
printf("%d:",i);
j=0;
while(num[j][i]!=-1)
{
printf(" %d",num[j][i]);
j++;
}
printf("\n");
}
}
/*print the result*/

void main()
{
char cmd1[5],cmd2[5];
int a,b,i,j,n;
scanf("%d",&n);
for(i=0;i<24;i++)
{
num[0][i]=i;
for(j=1;j<24;j++)
num[j][i]=-1;
}
while(scanf("%s",&cmd1)!=EOF)
{
if(!strcmp(cmd1,"move")||!strcmp(cmd1,"pile"))
{
scanf("%d%s%d",&a,&cmd2,&b);
if(a!=b&&a<24&&b<24&&a>=0&&b>=0)
{
if(!strcmp(cmd1,"move")&&!strcmp(cmd2,"onto"))
mov_onto(a,b);
else if(!strcmp(cmd1,"move")&&!strcmp(cmd2,"over"))
mov_over(a,b);
else if(!strcmp(cmd1,"pile")&&!strcmp(cmd2,"onto"))
pil_onto(a,b);
else if(!strcmp(cmd1,"pile")&&!strcmp(cmd2,"over"))
pil_over(a,b);
else;
}
else;
}
else if(!strcmp(cmd1,"quit"))
break;
else;
}
if(n>0&&n<25)
{
printf("\n");
out(n);
}
else;
}
[/c]

[Moni]

Have You Checked If Any Wrong Command Is Given ???

[james-b]

yes..
sort like "pull 1213 onto 121" "moves 4 ontoover 3 " "pile -444 onto 321"
so...what else I haven't noticed?

[Moni]

Is this ignored ???

Have you used BACK like functions ???

[epsilon0]

i just validated this problem today

a few things:

1- your program is too long

2- there are NO wrong commands like "push 123 on top of 456"... all the commands look like
[move|pile] number [onto|over] number
where 0< number < 25

3- i found this function in your program:

void out(int a)
{
int i,j;
for(i=0;i<a;i++)
{
if(i<10) /* this is useless */
printf(" %d:",i); /* this is wrong */
else
printf("%d:",i); /* yes, this is correct */
j=0;
while(num[j]!=-1)
{
printf(" %d",num[j]); /* this is correct */
j++;
}
printf("\n"); /* this is correct */
}
}

why the heck would you do printf(" %d",i)? read the output format carefully for this problem. NO line of output should start with " " (space).

[james-b]

I'm trying to get my program easier with your advice.
Thanks.

[passwd]

hi,

I'm trying to solve problem 101, but I'm getting wrong answer,
anyone can help me ?

Code: Select all

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*#define DEBUG*/

typedef struct celula {
 int key;
 struct celula *prox;
 struct celula *ant;
} node;
typedef node *lista;

void listKill(lista l[],int n);
void exception(char *msg);
void imprime(lista l[],int n);
lista blockSearch(lista l,int x);
lista listInsertFront(lista l,int x);

int main() {

 char linha[18];
 char cmd[5];
 char cmd2[5];
 int i;
 int n;
 int a;
 int b;

 scanf("%d",&n);

 {
 lista blocks[n];
 for(i=0;i<n;i++) blocks[i]=NULL;
 for(i=0;i<n;i++) blocks[i]=listInsertFront(blocks[i],i);

 while(scanf("%s",cmd)!=-1) {
    if(strcmp("quit",cmd)==0) break;
    scanf("%d %s %d",&a,cmd2,&b);
    /* verifica se comando eh valido*/
    if ( (a>n) || (b>n) ) continue;
    if ( (a<0) || (b<0) ) continue;
    if(a==b) continue;
    else if( (strcmp("move",cmd)==0) && (strcmp("onto",cmd2)==0) ) {
      /* move a onto b */
      lista blockA=NULL,blockB=NULL;
      lista a1,p1,p2;
      int j=0,k=0;

      /* procura pelo bloco a */
      while( (blockA==NULL) && (j<n) ) {
        blockA=blockSearch(blocks[j],a);
        ++j;
      }
      /* procura pelo bloco b */
      while( (blockB==NULL) && (k<n) ) {
        blockB=blockSearch(blocks[k],b);
        ++k;
      }

      /* verifica se estao na mesma pilha */
      if(j==k) continue;
      /* executa o comando */
      p1=blockA->prox;
      a1=blockA->ant;
      p2=blockB->prox;

      if(p1!=NULL) p1->ant=a1;
      if(a1!=NULL) a1->prox=p1;

      blockA->prox=p2;
      if(p2!=NULL) p2->ant=blockA;
      blockA->ant=blockB;
      blockB->prox=blockA;

      /*verifica se o bloco A eh o primeiro da pilha */
      if( (a1==NULL) && (p1==NULL) ) blocks[j-1]=NULL;
      else if( (a1==NULL) && (p1!=NULL) ) blocks[j-1]=p1;
    }
    else if( (strcmp("move",cmd)==0) && (strcmp("over",cmd2)==0) ) {
      /* move a over b */
      lista blockA=NULL,blockB=NULL;
      lista a1,p1,aux;
      int j=0,k=0;

      /* procura pelo bloco a */
      while( (blockA==NULL) && (j<n) ) {
        blockA=blockSearch(blocks[j],a);
        ++j;
      }
      /* procura pelo bloco b */
      while( (blockB==NULL) && (k<n) ) {
        blockB=blockSearch(blocks[k],b);
        ++k;
      }
      /* verifica se estao na mesma pilha */
      if(j==k) continue;
      /* executa o comando */
      p1=blockA->prox;
      a1=blockA->ant;
      aux=blockB;
      while(aux->prox!=NULL) {
         aux=aux->prox;
      }
      if(p1!=NULL) p1->ant=a1;
      if(a1!=NULL) a1->prox=p1;
      blockA->prox=NULL;
      blockA->ant=aux;
      aux->prox=blockA;
      /* verifica se o bloco A eh o primeiro da pilha */
      if( (a1==NULL) && (p1==NULL) ) blocks[j-1]=NULL;
      else if( (a1==NULL) && (p1!=NULL) ) blocks[j-1]=p1;
    }
    else if( (strcmp("pile",cmd)==0) && (strcmp("onto",cmd2)==0) ) {
      /* pile a onto b */
      lista blockA=NULL,blockB=NULL;
      lista a1,p1,p2;
      int j=0,k=0;

      /* procura pelo bloco a */
      while( (blockA==NULL) && (j<n) ) {
        blockA=blockSearch(blocks[j],a);
        ++j;
      }
      /* procura pelo bloco b */
      while( (blockB==NULL) && (k<n) ) {
        blockB=blockSearch(blocks[k],b);
        ++k;
      }
      /* verifica se estao na mesma pilha */
      if(j==k) continue;
      /* executa o comando */
      p1=blockA;
      a1=blockA->ant;
      p2=blockB->prox;
      while(p1->prox!=NULL) {
         p1=p1->prox;
      }
      if(a1!=NULL) a1->prox=NULL;
      blockA->ant=blockB;
      blockB->prox=blockA;
      p1->prox=p2;
      if(p2!=NULL) p2->ant=p1;

      /* verifica se o bloco A eh o primeiro da pilha */
      if(a1!=NULL) a1->prox=NULL;
      else blocks[j-1]=NULL;
    }
    else if( (strcmp("pile",cmd)==0) && (strcmp("over",cmd2)==0) ) {
      /* pile a over b */
      lista blockA=NULL,blockB=NULL;
      lista a1,aux;
      int j=0,k=0;

      /* procura pelo bloco a */
      while( (blockA==NULL) && (j<n) ) {
        blockA=blockSearch(blocks[j],a);
        ++j;
      }
      /* procura pelo bloco b */
      while( (blockB==NULL) && (k<n) ) {
        blockB=blockSearch(blocks[k],b);
        ++k;
      }
      /* verifica se estao na mesma pilha */
      if(j==k) continue;
      /* executa o comando */
      a1=blockA->ant;
      aux=blockB;
      while(aux->prox!=NULL) {
         aux=aux->prox;
      }
      blockA->ant=aux;
      aux->prox=blockA;
      if(a1!=NULL) a1->prox=NULL;
      /* verifica se o bloco A eh o primeiro da pilha */
      else blocks[j-1]=NULL;
    }

  
      #ifdef DEBUG
         imprime(blocks,n);
      #endif

  }

  imprime(blocks,n);
  listKill(blocks,n);

  }
  return 0;
}

void exception(char *msg) {
   printf("%s",msg);
   exit(1);
}

void listKill(lista l[],int n) {
  int i;
  for(i=0;i<n;i++) {
    if(l[i]!=NULL) {
      lista p=l[i];
      while(p!=NULL) {
        lista aux=p->prox;
        free(p);
        p=aux;
      }
    }
  }
}

void imprime(lista l[],int n) {
  int i;
  for(i=0;i<n;i++) {
    if(l[i]==NULL) printf("%d:\n",i);
    else {
      lista p=l[i];
      printf("%d: ",i);
      while(p->prox!=NULL) {
        printf("%d ",p->key);
        p=p->prox;
      }
      printf("%d\n",p->key);
    }
  }
}

lista blockSearch(lista l,int x) {
  lista p=l;
  while(p!=NULL) {
    if(p->key==x) return p;
    p=p->prox;
  }
  return NULL;
}

lista listInsertFront(lista l,int x) {
  lista novo = (node*) (malloc(sizeof(novo)));
  if(!novo) exception("\n\nMemoria insuficiente para alocar novo no !!\n\n");
  novo->key=x;
  novo->prox=l;
  novo->ant=NULL;
  l=novo;
  return novo;
}

[/c]

[27584NX]

I made a time expensive solution for this problem, basically working with an struct with two integers, storing the pile and the pile position do the n indexes of my struct array, and spend a lot of time debugging my program.

Are lists the fastest way to do it? if (true) how do I work with lists?

[shaka]

May someone help me..............

[cpp]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*
* struct node is used to construct array B
* struct node B[];
* There will be some link_lists in B[]
* start from some head_node in H[], end at -1
*/
struct node
{
// no "int value" is the result of that "i is the value of B"
int parent; // parent link in B
int child; // child link in B
};

/*
* 0: B[H[0].start] -> ...
* 1: B[H[1].start] -> ...
* 2: B[H[2].start] -> ...
* 3:
* ...
* n-1: B[H[n-1].start] -> ...
*
* parent of B[H.start] = i+n;
* so if one node B[j], its parent = x>n
* it must be head node of H[x-n]
*/

int n;
struct node B[24];
int H[24];

// find out which H contains $who
int inWhichH(int who)
{
do
{
who = B[who].parent;
} while(who<n);

return (who-n);
}

// all child of $who will be sent back to their initial position
void allChildBackInit(int who)
{
int who_p = who; // the point on the who_H
int cp; // child point
int cpc; // child point.child
int cp_r; // root node of H[cp]
while(B[who_p].child != -1)
{
cp = B[who_p].child;
cpc = B[cp].child;
// crossing cp
B[who_p].child = cpc;
// back crossing cp
if(cpc != -1)
B[cpc].parent = who_p;
//sent cp back to its initial position
cp_r = H[cp];
if(cp_r == -1)
{
H[cp] = cp;
B[cp].parent = cp+n;
B[cp].child = -1;
}
else
{
while(B[cp_r].child != -1) // here cp_r is not used for root
cp_r = B[cp_r].child;
B[cp_r].child = cp;
B[cp].parent = cp_r;
B[cp].child = -1;
}
}
}

int main( void )
{
// variable declaration
int i,j,k;


scanf( "%d\n",&n );
if(n<=0 || n>24)
return 0;

for( i=0 ; i<n ; i++ )
{
H = i;

B.parent = i+n;
B.child = -1;
}

char token[ 20 ];
char *move = "move";
char *pile = "pile";
char *onto = "onto";
char *over = "over";
char *quit = "quit";
int from,to;
int from_H, to_H;

while( 1 )
{
scanf( "%s",token );

if( strcmp( token,move ) ==0 )
{
scanf( "%s",token );
from = atoi( token );
scanf( "%s",token );

if( strcmp( token,onto ) ==0 )
{
scanf( "%s",token );
to = atoi( token );
if(from == to) continue;

// move from onto to
from_H = inWhichH(from);
to_H = inWhichH(to);
if(from_H == to_H) continue;

// move all blocks on $from $to to their initial position
allChildBackInit(from);
allChildBackInit(to);

if(B[from].parent > n)
H[from_H] = -1;
else
B[B[from].parent].child = -1;
B[from].parent = to;
B[from].child = -1;
B[to].child = from;
}
else if( strcmp( token,over ) ==0 )
{
scanf( "%s",token );
to = atoi( token );
if(from == to) continue;

// move from over to
from_H = inWhichH(from);
to_H = inWhichH(to);
if(from_H == to_H) continue;

// move all blocks on $from to their initial position
allChildBackInit(from);

j = to;
while(B[j].child != -1)
j = B[j].child;
if(B[from].parent > n)
H[from_H] = -1;
else
B[B[from].parent].child = -1;
B[from].parent = j;
B[from].child = -1;
B[j].child = from;
}
}
else if( strcmp( token,pile ) ==0 )
{
scanf( "%s",token );
from = atoi( token );
scanf( "%s",token );

if( strcmp( token,onto ) ==0 )
{
scanf( "%s",token );
to = atoi( token );
if(from == to) continue;

//pile from onto to
from_H = inWhichH(from);
to_H = inWhichH(to);
if(from_H == to_H) continue;

// move all blocks on $to to their initial position
allChildBackInit(to);

i = B[from].parent;
if(i>n)
H[from_H] = -1;
else
B.child = -1;
B[from].parent = to;
B[to].child = from;
}
else if( strcmp( token,over ) ==0 )
{
scanf( "%s",token );
to = atoi( token );
if(from == to) continue;

// pile from over to
from_H = inWhichH(from);
to_H = inWhichH(to);
if(from_H == to_H) continue;

j = to;
while(B[j].child != -1)
j = B[j].child;
if(B[from].parent>n)
H[from_H] = -1;
else
B[B[from].parent].child = -1;
B[from].parent = j;
B[j].child = from;
}
}
else if( strcmp( token,quit ) ==0 )
{
for(i=0 ; i<n ; i++)
{
printf("%d:",i);
j = H;
while(j != -1)
{
printf(" %d",j);
j = B[j].child;
}
printf("\n");
}
break;
}
}

return 0;
}


[/cpp]