101 - The Blocks Problem

[htl]

Thanks for your helping of debuging. I got AC. And I'll change my way of asking questions.

[How-Yun Yin]

I think my code is correct
I have test my code with sample input
and i think the result is corredt,too!
but I always get the "Wrong Answer" from Online Judge
who can help me test my code and result?
input

Code: Select all

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

output

Code: Select all

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

[cpp]#include<iostream.h>
#include<string.h>
class block{
private:
int Index;
public:
block(){
}
block(int index){
setIndex(index);
}
int getIndex(){
return Index;
}
void setIndex(int index){
Index=index;
}
};
class stack{
private:
int mdata[25];
int sp;
public:
stack(){
sp=0;
}
void push(int data){
if(sp==25)return;
mdata[sp++]=data;
}
int pop(){
if(sp==0)return 0;
return mdata[--sp];
}
int getData(){
if(sp==0)return 0;
return mdata[sp-1];
}
int getSize(){
return sp;
}
void print(){
for(int i=0;i<sp;i++){
cout<<" "<<mdata;
}
}
};
class robot{
private:
block *bl;
stack *st;
int n;
public:
robot(int n,stack st[],block bl[]){
this->n=n;
this->bl=bl;
this->st=st;
}
void moveonto(int bsrc,int bdes){
int isrc,ides;
stack tmp1,tmp2;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp1.push((st+isrc)->pop());
}

while((st+ides)->getData()!=bdes){
tmp2.push((st+ides)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp1.getSize()!=0){
(st+isrc)->push(tmp1.pop());
}

while(tmp2.getSize()!=0){
(st+ides)->push(tmp2.pop());
}

}
void moveover(int bsrc,int bdes){
int isrc,ides;
stack tmp;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp.push((st+isrc)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp.getSize()!=0){
(st+isrc)->push(tmp.pop());
}
}
void pileonto(int bsrc,int bdes){
int isrc,ides;
stack tmp1,tmp2;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp1.push((st+isrc)->pop());
}
while((st+ides)->getData()!=bdes){
tmp2.push((st+ides)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp1.getSize()!=0){
(bl+tmp1.getData())->setIndex(ides);
(st+ides)->push(tmp1.pop());
}
while(tmp2.getSize()!=0){
(st+ides)->push(tmp2.pop());
}
}
void pileover(int bsrc,int bdes){
int isrc,ides;
stack tmp;
if(bsrc>n-1||bdes>n-1)return;
isrc=(bl+bsrc)->getIndex();
ides=(bl+bdes)->getIndex();
if(isrc==ides)return;
while((st+isrc)->getData()!=bsrc){
tmp.push((st+isrc)->pop());
}
(st+ides)->push((st+isrc)->pop());
(bl+bsrc)->setIndex(ides);
while(tmp.getSize()!=0){
(bl+tmp.getData())->setIndex(ides);
(st+ides)->push(tmp.pop());
}
}
void print(){
for(int i=0;i<n;i++){
cout<<i<<":";
(st+i)->print();
cout<<endl;
}
}
};
int main(void){
char cmd1[5],cmd2[5];
int bsrc,bdes;
int n;
robot *r;
block *bl;
stack *st;
cin>>n;

if(n<1||n>24)return 1;
bl=new block[n];
st=new stack[n];
for(int i=0;i<n;i++){
(bl+i)->setIndex(i);
(st+i)->push(i);
}
r=new robot(n,st,bl);
while(1){
cin>>cmd1;
if(strcmp(cmd1,"quit")==0)break;
cin>>bsrc>>cmd2>>bdes;
if(bsrc==bdes)continue;
if(strcmp(cmd1,"move")==0){
if(strcmp(cmd2,"onto")==0){
r->moveonto(bsrc,bdes);
}
if(strcmp(cmd2,"over")==0){
r->moveover(bsrc,bdes);
}
}
if(strcmp(cmd1,"pile")==0){
if(strcmp(cmd2,"onto")==0){
r->pileonto(bsrc,bdes);
}
if(strcmp(cmd2,"over")==0){
r->pileover(bsrc,bdes);

}
}
}
r->print();

return 0;
}[/cpp]

[1_UtterBlue]

You may have mistaken the words in the problems. See difference between moveonto and pileonto may be of help.

[1_UtterBlue]

[pascal]
Program Blocks(input,output);
Type
pointer=^node;
node=record
num,cur_stack:integer;
prev,next:pointer;
end;

Var n:integer;
cmd:string;
queue:array[0..24] of node;
boxes:array[0..24] of node;

Procedure Display;
var i,j:integer;
p:pointer;
begin
for i:=0 to n-1 do
begin
write(i,':');
if boxes.next<>NIL then
begin
p:=boxes.next;
while p<>NIL do
begin write(' ',p^.num);p:=p^.next; end;
end;
writeln;
end;
end;

Procedure Initialize;
Var i:integer;
begin
for i:=0 to n-1 do
begin
queue.num:=i;
queue.next:=NIL;
queue.prev:=@boxes;
queue.cur_stack:=i;
boxes.next:=@queue;
end;
end;

Procedure moveonto(a,c:integer);
begin
(queue[a].prev^).next:=queue[a].next;
if queue[a].next<>NIL then
(queue[a].next^).prev:=queue[a].prev;
queue[a].cur_stack:=queue[c].cur_stack;
queue[a].next:=queue[c].next;
(queue[c].next^).prev:=@queue[a];
queue[c].next:=@queue[a];
queue[a].prev:=@queue[c];
end;

Procedure moveover(a,c:integer);
Var p:pointer;
begin
(queue[a].prev^).next:=queue[a].next;
if queue[a].next<>NIL then
(queue[a].next^).prev:=queue[a].prev;
queue[a].cur_stack:=queue[c].cur_stack;
p:=@queue[c];
While p^.next<>NIL do p:=p^.next;
queue[a].next:=NIL;
queue[a].prev:=p;p^.next:=@queue[a];
end;

Procedure pileover(a,c:integer);
Var p:pointer;
begin
queue[a].prev^.next:=NIL;
p:=@queue[a];
While p^.next<>NIL do
begin
queue[p^.num].cur_stack:=queue[c].cur_stack;
p:=p^.next;
end;
p^.cur_stack:=queue[c].cur_stack;
p:=@queue[c];
While p^.next<>NIL do p:=p^.next;
p^.next:=@queue[a];
queue[a].prev:=p;
end;

Procedure pileonto(a,c:integer);
Var p:pointer;
begin
queue[a].prev^.next:=NIL;
p:=@queue[a];
While p^.next<>NIL do
begin
queue[p^.num].cur_stack:=queue[c].cur_stack;
p:=p^.next;
end;
p^.cur_stack:=queue[c].cur_stack;
p^.next:=queue[c].next;
queue[c].next^.prev:=p;
queue[c].next:=@queue[a];
queue[a].prev:=@queue[c];
end;

Function legal(a,c:integer):boolean;
begin
legal:=true;
if (a=c) or (queue[a].cur_stack=queue[c].cur_stack) then
begin legal:=false;exit;end;
if (a<0) or (a>n-1) or (c<0) or (c>n-1) then legal:=false;
end;

Procedure Cmd_Parse;
Var command:string;
num1,num2,t,m:integer;
begin
command:=copy(cmd,1,4);
delete(cmd,1,5);
t:=1;
while cmd[t]<>' ' do t:=t+1;
Val(copy(cmd,1,t-1),num1,m);
delete(cmd,1,t);
command:=command+copy(cmd,1,4);
delete(cmd,1,5);
Val(cmd,num2,m);
If legal(num1,num2) then
begin
if command='moveonto' then moveonto(num1,num2)
else if command='moveover' then moveover(num1,num2)
else if command='pileonto' then pileonto(num1,num2)
else if command='pileover' then pileover(num1,num2);
end;
end;
begin
Readln(n);
Initialize;
Readln(cmd);
While cmd<>'quit' do
begin
Cmd_Parse;
Readln(cmd);
end;
Display;
end.

[/pascal]
I got the answer as
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

What's wrong? I used fixed array to store all the boxes. (Array queue) and array BOX is used to store the link for each stack. Every stack is started with a head node.
Anyone's help is appreciated! Thanks.

[Admiral]

Array pre means the previous box of each box, if there's not a previous box then set as -1, the same as other arrays. Array first means the first box of each stack, and array position means the position of every box.
[c]#include <stdio.h>

void main(void)
{
short i,n,a,b,p;
short pre[25],next[25],first[25],position[25];
char comm1[5],comm2[5];

scanf("%d",&n);
for (i=0;i<n;i++)
{
position=first=i;
pre=next=-1;
}
scanf("%s",comm1);
while (comm1[0]!='q')
{
scanf("%d%s%d",&a,comm2,&b);
if (a!=b && position[a]!=position)
{
if (comm1[0]=='m')
{
if (comm2[1]=='n')
{
if (pre[a]!=-1) next[pre[a]]=next[a];
if (next[a]!=-1) pre[next[a]]=pre[a];
if (first[position[a]]==a) first[position[a]]=next[a];
pre[a]=b;
next[a]=next;
next=a;
if (next[a]!=-1) pre[next[a]]=a;
position[a]=position;
}//move onto
else
{
if (pre[a]!=-1) next[pre[a]]=next[a];
if (next[a]!=-1) pre[next[a]]=pre[a];
if (first[position[a]]==a) first[position[a]]=next[a];
p=b;
while (next[p]!=-1) p=next[p];
next[a]=-1;
next[p]=a;
pre[a]=p;
position[a]=position;
}//move over
}
else
{
if (comm2[1]=='n')
{
if (pre[a]!=-1) next[pre[a]]=-1;
if (first[position[a]]==a) first[position[a]]=-1;
p=a;
while (next[p]!=-1)
{
position[p]=position;
p=next[p];
}
position[p]=position;
next[p]=next;
if (next[p]!=-1) pre[next[p]]=p;
next=a;
pre[a]=b;
}//pile onto
else
{
if (pre[a]!=-1) next[pre[a]]=-1;
if (first[position[a]]==a) first[position[a]]=-1;
p=b;
while (next[p]!=-1) p=next[p];
next[p]=a;
pre[a]=p;
while (next[p]!=-1)
{
p=next[p];
position[p]=position;
}
}//pile over
}
}
scanf("%s",comm1);
}
for (i=0;i<n;i++)
{
printf("%d:",i);
p=first;
while (p!=-1)
{
printf(" %d",p);
p=next[p];
}
printf("\n");
}
}[/c]

[How-Yun Yin]

Code: Select all

all example:
0: 1 2 3 4 5
2: 6 7 8 9 0

Code: Select all

move 8 onto 2
0: 1 2 8 3 4 5
2: 6 7 9 0

Code: Select all

move 8 over 2
0: 1 2 3 4 5 8
2: 6 7 9 0

Code: Select all

pile 8 onto 2
0: 1 2 8 9 0 3 4 5
2: 6 7

Code: Select all

pile 8 over 2
0: 1 2 3 4 5 8 9 0
2: 6 7

is that right?
who can tell me?

[nayaya]

I think your size of the two arrays should be much much bigger. I got the same reply on 202, and I got AC after I enlarged the array. Try!

[1_UtterBlue]

I've enlarged my array upto 100. And I've spent the annoying 30m typing different awful command to test my program, nothing wrong with that!!! What's wrong lying there? That annoying? There must be something big and huge? Wish I was Harry Potter.

[1_UtterBlue]

Yes, that's right.

[zalileo]

it should be that:

Code: Select all

all example: 
0: 0 1 2 3 4 
5: 5 6 7 8 9 

Code: Select all

move 8 onto 2 
0: 0 1 2 8
3: 3
4: 4 
5: 5 6 7
9: 9

Code: Select all

move 8 over 2 
0: 0 1 2 3 4 8
5: 5 6 7
9: 9

Code: Select all

pile 8 onto 2 
0: 0 1 2 8 9
3: 3
4: 4
5: 5 6 7

Code: Select all

pile 8 over 2 
0: 0 1 2 3 4 8 9
5: 5 6 7

[How-Yun Yin]

finally....i get it.....
thank you very very much!!!!!!!!!

[jamesng]

Hi guys, sorry to trouble you.
I've tested my code with the above cases and got the stated results.
However, I still get 'Wrong Answer' from the judge
May I know is there any exception cases that I may not have taken care of?
Thank you very much.

James

[jamesng]

Just found out the mistake I made. Forgot to ignore the commands for blocks in the same stack.

[Spike]

Okay... what if the initial configuration is like this

0: 5 0
1: 1
2: 2
3: 3
4: 4
5:

and the command is "move 4 onto 5"

You're supposed to move all blocks on top of 4 and 5 to their original positions. However, 0 is in it's original position.

Do you move 0 under 5? You shouldn't ignore it because 4 and 5 are not in the same pile.

Please help me figure this one out.

[Spike]

nevermind... I'm stupid.
you could never get into that position, because you couldn't get 5 there.

Therefore, you can correctly assume that the block on the bottom of a pile is always going to be the same block # as the pile number.