101 - The Blocks Problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

This is taken from the problem-statement:
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.
Looks like you didn't completely take care of that in your code, or did I miss anything ... ???

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Thank You Rong

Post by Nick »

Hi, yes my code was wrong...but i've fixed it and solve the problem with my new code

The mistake was at handling command "pile onto" and maybe some other mistakes. So....thx anyway for your help Rong
evanmars
New poster
Posts: 4
Joined: Mon Mar 10, 2003 10:13 pm

oops

Post by evanmars »

previous post deleted - wrong place
evanmars
New poster
Posts: 4
Joined: Mon Mar 10, 2003 10:13 pm

Works for me but not for judge

Post by evanmars »

This works for me using MSVC++ v6.0, but the online judge says:
"Your program has died with signal 11 (SIGSEGV). Meaning: Invalid memory reference"

Any ideas?

///code starts here///

// @JUDGE_ID: ******* 101 C++

#include <iostream.h>

struct Location
{
int s[2]; /*source position*/
int d[2]; /*destination position*/
bool same;
};

/// FUNCTION PROTOTYPES ///

Location find_ls(int&, int&, int**, int);
void clear_source(Location&, int** c, int);
void clear_destination(Location&, int**, int);
void moveonto(Location&, int**, int);
void moveover(Location&, int**, int);
void pileonto(Location&, int**, int);
void pileover(Location&, int**, int);

////////////////////////////////////////////////////


int main()
{
bool done = false;
int bq, object1, object2, ins;
char instruction1[4];
char instruction2[4];
int** bl;
Location l;

cin >> bq;
bl = new int*[bq];
for(int x = 0; x < bq; x++)
{
bl[x] = new int[bq];
for(int y = 1; y < bq; y++)
bl[x][y] = bq + 1;
bl[x][0] = x;
}

while(!done)
{
cin >> instruction1;
if(instruction1[0] == 'm') // move?
ins = 1;
else if(instruction1[0] == 'p') // pile?
ins = 2;
else ins = 3;


if(ins != 3)
{
cin >> object1 >> instruction2 >> object2;

if(object1 != object2)// if they aren't the same block
{
l = find_ls(object1,object2,bl,bq);// get position of blocks

if(!l.same)// if the aren't in the same stack
{
if(ins == 1) // move
{
if(object1 > 0 && object2 > 0) //ignore if either block number is less than 1
{
if(object1 < bq && object2 < bq)// ignore if either block number is not less that number of blocks
{
if(instruction2[1] == 'n') // onto
moveonto(l,bl,bq);
else
moveover(l,bl,bq);
}
}

}
else if(ins == 2)
{
if(object1 > 0 && object2 > 0)
{
if(object1 < bq && object2 < bq)
{
if(instruction2[1] == 'n')
pileonto(l,bl,bq);
else
pileover(l,bl,bq);
}
}
}
}
}
}
else
done = true;// finished receiving moves
}

for(int z = 0; z < bq; z++)
{
cout << z << ":";
for(int y = 0; y < bq; y++)
{
if(bl[z][y] > bq)
break;
cout << " " << bl[z][y];
}
cout << "\n";

}

return 0;
}

/// FUNCTION DEFINITIONS ///////////
Location find_ls(int& a, int& b, int** bl, int length)
{
int found = 0;
Location places;

places.same = false;

for(int x = 0; x < length; x++)
{
for(int y = 0; y < length; y++)
{
if(bl[x][y] == b)
{
places.d[0] = x;
places.d[1] = y;
found += 1;
}
if(bl[x][y] == a)
{
places.s[0] = x;
places.s[1] = y;
found += 1;
}
if(found == 2)
break;
}
if(found == 2)
break;
}

if(places.s[0] == places.d[0])
places.same = true;

return places;
}

void clear_source(Location& l, int** bl, int length)
{
int i = 0;
int j = 0;
int temp = 0;
int* work;
work = new int[length];

for(int x = 0; x < length-1; x++)
work[x] = length + 1;

j = l.s[1] + 1;

for(int z = j; z < length-1; z++)
{
work[i++] = bl[l.s[0]][j];
bl[l.s[0]][j++] = length + 1;
}


for(int a = length-2; a >= 0; a--)
{
if(work[a] != length+1)
{
for(int y = 0; y < length-1; y++)
{
if(bl[work[a]][y] == length+1)
{
bl[work[a]][y] = work[a];
break;
} }
}
}
delete[]work;
}

void clear_destination(Location& l, int** bl, int length)
{
int i = 0;
int j;
int* work;
work = new int[length];

for(int x = 0; x < length-1; x++)
work[x] = length+1;

j = (l.d[1]) + 1;
do
{
work[i++] = bl[l.d[0]][j];
bl[l.d[0]][j++] = length+1;
}while(bl[l.d[0]][j] != length+1);

for(int z = length-2 ; z >= 0; z--)
{
if(work[z] != length+1)
{
for(int y = 0; y < length; y++)
{
if(bl[work[z]][y] == length+1)
{
bl[work[z]][y] = work[z];
break;
}
}
}
}
delete[]work;
}


void moveonto(Location& l, int** bl, int length)
{
clear_source(l, bl, length);
clear_destination(l, bl, length);
bl[l.d[0]][(l.d[1]) + 1] = bl[l.s[0]][l.s[1]];
bl[l.s[0]][l.s[1]] = length+1;
}


void moveover(Location& l, int** bl, int length)
{
clear_source(l, bl, length);
for(int x = l.d[1]; x < length; x++)
{
if(bl[l.d[0]][x] == length+1)
{
bl[l.d[0]][x] = bl[l.s[0]][l.s[1]];
bl[l.s[0]][l.s[1]] = length+1;
break;
}
}
}

void pileonto(Location& l, int** bl, int length)
{
int i = (l.d[1]) + 1;
clear_destination(l, bl, length);
for(int x = l.s[1]; x < length; x++)
{
if (bl[l.s[0]][x] == length+1)
break;
bl[l.d[0]][i++] = bl[l.s[0]][x];
bl[l.s[0]][x] = length+1;
}
}


void pileover(Location& l, int** bl, int length)
{
int i;
for(int x = l.d[1]; x < length; x++)
{
if(bl[l.d[0]][x] == length+1)
{
i = x;
break;
}
}
for(int z = l.s[1]; z < length; z++)
{
bl[l.d[0]][i++] = bl[l.s[0]][z];
bl[l.s[0]][z] = length+1;
}
}
Last edited by evanmars on Tue Mar 11, 2003 2:33 pm, edited 1 time in total.
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

if you got SIGSEGV first you must check your array. :-?
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

One word of warning: Don't publish your ID!
Others might misuse it for their own malicious purposes.
(Simply edit your message to get rid of it.)
evanmars
New poster
Posts: 4
Joined: Mon Mar 10, 2003 10:13 pm

?? I'm stuck

Post by evanmars »

Hisoka wrote:if you got SIGSEGV first you must check your array. :-?
Check it for what. As I said, "It works for me." Everything I try works, I'm not sure how to look for a problem that doesn't show up for me.

P.S. Thanks for the advice, Little Joey.
Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

yeah, evanmars RE didn't mean your solution wrong. Because before I solve this problem My solution get more true I/O, and that means my solution works fine to me too, but I got SIGSEGV. And I check my array and get AC.
Izmunuti
New poster
Posts: 10
Joined: Mon Feb 10, 2003 7:22 am

Try this input

Post by Izmunuti »

Here's an input that breaks your program in two ways:
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
move 9 over 9
move 1 over 9
move 0 over 5
move 0 ontopof 6
relocate 6 before 3
quit
My code returns:
0:
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6 0
6:
7:
8:
9:
When I run your code I get:
Segmentation fault
Iz
Miguel Correia Ricardo
New poster
Posts: 9
Joined: Sat Nov 30, 2002 4:09 am
Contact:

101 SIGSEV and WORKS WITH ALL EXAMPLES!

Post by Miguel Correia Ricardo »

Hi, Judge replies to my solution SIGSEV? Why, is anything wrong with the Vectors?
[cpp]
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Index{
unsigned int x;
unsigned int y;
public:
Index (){}
Index(unsigned int x, unsigned int y):
x(x),
y(y)
{
}

Index(const Index& idx) {
Set(idx.X(),idx.Y());
}

void Set (unsigned int xPoint, unsigned int yPoint){
x = xPoint;
y = yPoint;
}

void Set(const Index& idx){
Set(idx.X(),idx.Y());
}

unsigned int X() const{
return x;
}

unsigned int Y() const{
return y;
}
};

class Blocks{
short n_blocks;
vector< vector<short> > blockWorld;

void init_blockWorld();
Index FindBlock(const short block);
void ReturnToInitialPosition(const Index& fix);

public:
Blocks()
{
}

Blocks(short n){
n_blocks = n;
init_blockWorld();
}

~Blocks()
{
}

void Set(const short n);
void MoveOnto(const short a, const short b);
void MoveOver(const short a, const short b);
void PileOnto(const short a, const short b);
void PileOver(const short a, const short b);
short NumBlocks();
void WriteWorld() const;
};

void Blocks::init_blockWorld (){
short init = 0;

blockWorld.resize(n_blocks);
for (unsigned int i = 0; i < blockWorld.size(); i++){
blockWorld.resize(n_blocks);
blockWorld[0] = init++;
for (unsigned int j = 1; j < blockWorld.size(); j++)
blockWorld[j] = -1;
}
}

Index Blocks::FindBlock (const short block){
Index fix;

for (unsigned int i = 0; i < blockWorld.size (); i++)
for (unsigned j = 0; j < blockWorld.size(); j++){
if (blockWorld[j] == block){
fix.Set(i,j);
break;
}
}
return fix;
}

void Blocks::ReturnToInitialPosition(const Index& fix){
short block;

for (unsigned int i = fix.Y(); i < blockWorld.size(); i++){
if (blockWorld[fix.X()] == -1) break;
else{
block = blockWorld[fix.X()];
blockWorld[fix.X()] = -1;
for (unsigned int j = 0; j < blockWorld[block].size(); j++)
if (blockWorld[block][j] == -1) {
blockWorld[block][j] = block;
break;
}
}
}
}

void Blocks::Set(const short n){
n_blocks = n;
init_blockWorld ();
}

void Blocks::MoveOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
Index Temp;
unsigned int index=1;

if ((fixA.X() == fixB.X()) || (a==b)) return;

while ((blockWorld[fixA.X()][fixA.Y()+index] != -1)) {
Temp.Set(fixA.X(),fixA.Y()+index);
ReturnToInitialPosition(Temp);
index++;
}

index = 1;
while ((blockWorld[fixB.X()][fixB.Y()+index] != -1)){
Temp.Set(fixB.X(),fixB.Y()+index);
ReturnToInitialPosition(Temp);
index++;
}

blockWorld[fixA.X()][fixA.Y()] = -1;
blockWorld[fixB.X()][fixB.Y()+1] = a;
}

void Blocks::MoveOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
unsigned int index=1;
Index Temp;

if ((fixA.X() == fixB.X()) || (a==b)) return;

blockWorld[fixA.X()][fixA.Y()] = -1;

while ((blockWorld[fixA.X()][fixA.Y()+index] != -1)) {
Temp.Set(fixA.X(),fixA.Y()+index);
ReturnToInitialPosition(Temp);
index++;
}


for (unsigned int i = 0; i < blockWorld[fixB.X()].size(); i++)
if (blockWorld[fixB.X()] == -1){
blockWorld[fixB.X()][i] = a;
break;
}
}

void Blocks::PileOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
vector<short> SavePile;
int index=1;

if ((fixA.X() == fixB.X()) || (a==b)) return;

while (blockWorld[fixB.X()][fixB.Y()+index]!=-1){
SavePile.push_back (blockWorld[fixB.X()][fixB.Y()+1]);
blockWorld[fixB.X()][fixB.Y()+1]=-1;
index++;
}
blockWorld[fixB.X()][fixB.Y()]=-1;
index=0;
while(blockWorld[fixA.X()][fixA.Y()+index] != -1){
blockWorld[fixB.X()][fixB.Y()+index]= blockWorld[fixA.X()][fixA.Y()+index];
blockWorld[fixA.X()][fixA.Y()+index]=-1;
index++;
}

blockWorld[fixB.X()][fixB.Y()+index] = b;

index = 1;
for (unsigned int i = 0; i < SavePile.size(); i++){
for (unsigned int j = 0; j < blockWorld[SavePile[i]].size(); j++)
if (blockWorld[SavePile[i]][j] == -1) {
blockWorld[SavePile[i]][j] = SavePile[i];
break;
}
}
}

void Blocks::PileOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
Index OverB;
unsigned int index = 0;

if ((fixA.X() == fixB.X()) || (a==b)) return;

for(unsigned int i = fixB.Y()+1; i < blockWorld[fixB.X()].size(); i++){
if (blockWorld[fixB.X()][i]==-1){
OverB.Set(fixB.X(),i);
break;
}
}

index = 0;
for (unsigned int i = OverB.Y(); i < blockWorld[OverB.X()].size(); i++){
if (blockWorld[fixA.X()][fixA.Y()+index] == -1) break;
else{
blockWorld[OverB.X()][OverB.Y()+index] = blockWorld[fixA.X()][fixA.Y()+index];
blockWorld[fixA.X()][fixA.Y()+index] = -1;
index++;
}
}
}

short Blocks::NumBlocks (){
return n_blocks;
}

void Blocks::WriteWorld() const{
for(unsigned int i=0; i < blockWorld.size(); i++){
cout << i << ": ";
for(unsigned int j = 0; j < blockWorld[i].size(); j++){
if (blockWorld[i][j] == -1) break;
cout << blockWorld[i][j] << " ";
}
cout << endl;
}
}

int main(){
string cmd1;
string cmd2;
short a;
short b;
short n;
string line;
Blocks blockWorld;

cin >> n;
if ((n>0)&&(n<25)){
blockWorld.Set(n);
while ((cin >> cmd1) && (cmd1 != "quit")){
cin >> a >> cmd2 >> b;
if ((a>=0)&&(b>=0) && (a < blockWorld.NumBlocks()) && (b < blockWorld.NumBlocks())){
if ((cmd1 == "move") && (cmd2 == "onto"))
blockWorld.MoveOnto(a,b);
else if ((cmd1 == "move") && (cmd2 == "over"))
blockWorld.MoveOver(a,b);
else if ((cmd1 == "pile") && (cmd2 == "onto"))
blockWorld.PileOnto(a,b);
else if ((cmd1 == "pile") && (cmd2 == "over"))
blockWorld.PileOver(a,b);
}
}
blockWorld.WriteWorld();
}
}
[/cpp]

Thank you for any help available
Thanks,
Miguel Correia Ricardo
E_mail:miguel_ricardo@hotmail.com
Miguel Correia Ricardo
New poster
Posts: 9
Joined: Sat Nov 30, 2002 4:09 am
Contact:

OK REWRITTEN CODE....!!! Still Have the same PROBLEM!

Post by Miguel Correia Ricardo »

[cpp]
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Index{
unsigned int x;
unsigned int y;
public:
Index (){}
Index(unsigned int x, unsigned int y):
x(x),
y(y)
{
}

Index(const Index& idx) {
Set(idx.X(),idx.Y());
}

void Set (unsigned int xPoint, unsigned int yPoint){
x = xPoint;
y = yPoint;
}

void Set(const Index& idx){
Set(idx.X(),idx.Y());
}

unsigned int X() const{
return x;
}

unsigned int Y() const{
return y;
}
};

class Blocks{
short n_blocks;
vector< vector<short> > blockWorld;

void init_blockWorld();
Index FindBlock(const short block);
void ReturnToInitialPosition(const Index& fix);

public:
Blocks()
{
}

Blocks(short n){
n_blocks = n;
init_blockWorld();
}

~Blocks()
{
}

void Set(const short n);
void MoveOnto(const short a, const short b);
void MoveOver(const short a, const short b);
void PileOnto(const short a, const short b);
void PileOver(const short a, const short b);
short NumBlocks();
void WriteWorld() const;
};

void Blocks::init_blockWorld (){
short init = 0;

blockWorld.resize(n_blocks);
for (unsigned int i = 0; i < blockWorld.size(); i++){
blockWorld.resize(n_blocks);
blockWorld[0] = init++;
for (unsigned int j = 1; j < blockWorld.size(); j++)
blockWorld[j] = -1;
}
}

Index Blocks::FindBlock (const short block){
Index fix;

for (unsigned int i = 0; i < blockWorld.size (); i++)
for (unsigned j = 0; j < blockWorld.size(); j++){
if (blockWorld[j] == block){
fix.Set(i,j);
break;
}
}
return fix;
}

void Blocks::ReturnToInitialPosition(const Index& fix){
short block;

for (unsigned int i = fix.Y()+1; i < blockWorld.size(); i++){
if (blockWorld[fix.X()] == -1) break;
else{
block = blockWorld[fix.X()];
blockWorld[fix.X()] = -1;
for (unsigned int j = 0; j < blockWorld[block].size(); j++)
if (blockWorld[block][j] == -1) {
blockWorld[block][j] = block;
break;
}
}
}
}

void Blocks::Set(const short n){
n_blocks = n;
init_blockWorld ();
}

void Blocks::MoveOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));

if ((fixA.X() == fixB.X()) || (a==b)) return;

ReturnToInitialPosition(fixA);
ReturnToInitialPosition(fixB);
blockWorld[fixA.X()][fixA.Y()] = -1;
blockWorld[fixB.X()][fixB.Y()+1] = a;
}

void Blocks::MoveOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));

if ((fixA.X() == fixB.X()) || (a==b)) return;

blockWorld[fixA.X()][fixA.Y()] = -1;

ReturnToInitialPosition(fixA);

for (unsigned int i = fixB.Y()+1; i < blockWorld[fixB.X()].size(); i++)
if (blockWorld[fixB.X()] == -1){
blockWorld[fixB.X()][i] = a;
break;
}
}

void Blocks::PileOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
vector<short> SavePile;
int index=1;

if ((fixA.X() == fixB.X()) || (a==b)) return;

while (blockWorld[fixB.X()][fixB.Y()+index]!=-1){
SavePile.push_back (blockWorld[fixB.X()][fixB.Y()+index]);
blockWorld[fixB.X()][fixB.Y()+index]=-1;
index++;
}

index=1;
while(blockWorld[fixA.X()][fixA.Y()+index] != -1){
blockWorld[fixB.X()][fixB.Y()+index]= blockWorld[fixA.X()][fixA.Y()+index];
blockWorld[fixA.X()][fixA.Y()+index]=-1;
index++;
}

index = 1;
for (unsigned int i = 0; i < SavePile.size(); i++){
for (unsigned int j = 0; j < blockWorld[SavePile[i]].size(); j++)
if (blockWorld[SavePile[i]][j] == -1) {
blockWorld[SavePile[i]][j] = SavePile[i];
break;
}
}
}

void Blocks::PileOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
Index OverB;
unsigned int index = 0;

if ((fixA.X() == fixB.X()) || (a==b)) return;

for(unsigned int i = fixB.Y()+1; i < blockWorld[fixB.X()].size(); i++){
if (blockWorld[fixB.X()][i]==-1){
OverB.Set(fixB.X(),i);
break;
}
}

index = 0;
for (unsigned int i = OverB.Y(); i < blockWorld[OverB.X()].size(); i++){
blockWorld[OverB.X()][OverB.Y()+index] = blockWorld[fixA.X()][fixA.Y()+index];
blockWorld[fixA.X()][fixA.Y()+index] = -1;
index++;
}
}

short Blocks::NumBlocks (){
return n_blocks;
}

void Blocks::WriteWorld() const{
for(unsigned int i=0; i < blockWorld.size(); i++){
cout << i << ": ";
for(unsigned int j = 0; j < blockWorld[i].size(); j++){
if (blockWorld[i][j] == -1) break;
cout << blockWorld[i][j] << " ";
}
cout << endl;
}
}

int main(){
string cmd1;
string cmd2;
short a;
short b;
short n;
string line;
Blocks blockWorld;

cin >> n;
if ((n>0)&&(n<25)){
blockWorld.Set(n);
while ((cin >> cmd1) && (cmd1 != "quit")){
cin >> a >> cmd2 >> b;
if ((a>=0)&&(b>=0) && (a < blockWorld.NumBlocks()) && (b < blockWorld.NumBlocks())){
if ((cmd1 == "move") && (cmd2 == "onto"))
blockWorld.MoveOnto(a,b);
else if ((cmd1 == "move") && (cmd2 == "over"))
blockWorld.MoveOver(a,b);
else if ((cmd1 == "pile") && (cmd2 == "onto"))
blockWorld.PileOnto(a,b);
else if ((cmd1 == "pile") && (cmd2 == "over"))
blockWorld.PileOver(a,b);
}
}
blockWorld.WriteWorld();
}
}
[/cpp]
Thanks,
Miguel Correia Ricardo
E_mail:miguel_ricardo@hotmail.com
Miguel Correia Ricardo
New poster
Posts: 9
Joined: Sat Nov 30, 2002 4:09 am
Contact:

I got Acepted

Post by Miguel Correia Ricardo »

Here is the code correct and much more simplified than the previous one:
[cpp]
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Index{
unsigned int x;
unsigned int y;
public:
Index (){}
Index(unsigned int x, unsigned int y):
x(x),
y(y)
{
}

Index(const Index& idx) {
Set(idx.X(),idx.Y());
}

void Set (unsigned int xPoint, unsigned int yPoint){
x = xPoint;
y = yPoint;
}

void Set(const Index& idx){
Set(idx.X(),idx.Y());
}

unsigned int X() const{
return x;
}

unsigned int Y() const{
return y;
}
};

class Blocks{
short n_blocks;
vector< vector<short> > blockWorld;

void init_blockWorld();
Index FindBlock(const short block);
void ReturnToInitialPosition(const Index& fix);

public:
Blocks()
{
}

Blocks(short n){
n_blocks = n;
init_blockWorld();
}

~Blocks()
{
}

void Set(const short n);
void MoveOnto(const short a, const short b);
void MoveOver(const short a, const short b);
void PileOnto(const short a, const short b);
void PileOver(const short a, const short b);
short NumBlocks();
void WriteWorld() const;
};

void Blocks::init_blockWorld (){
short init = 0;

blockWorld.resize(n_blocks);
for (unsigned int i = 0; i < blockWorld.size(); i++){
blockWorld.resize(n_blocks);
blockWorld[0] = init++;
for (unsigned int j = 1; j < blockWorld.size(); j++)
blockWorld[j] = -1;
}
}

Index Blocks::FindBlock (const short block){
Index fix;

for (unsigned int i = 0; i < blockWorld.size (); i++)
for (unsigned j = 0; j < blockWorld.size(); j++){
if (blockWorld[j] == block){
fix.Set(i,j);
break;
}
}
return fix;
}

void Blocks::ReturnToInitialPosition(const Index& fix){
short block;

for (unsigned int i = fix.Y()+1; i < blockWorld.size(); i++){
if (blockWorld[fix.X()] == -1) break;
else{
block = blockWorld[fix.X()];
blockWorld[fix.X()] = -1;
for (unsigned int j = 0; j < blockWorld[block].size(); j++)
if (blockWorld[block][j] == -1) {
blockWorld[block][j] = block;
break;
}
}
}
}

void Blocks::Set(const short n){
n_blocks = n;
init_blockWorld ();
}

void Blocks::MoveOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));

if ((fixA.X() == fixB.X()) || (a==b)) return;

ReturnToInitialPosition(fixA);
ReturnToInitialPosition(fixB);
blockWorld[fixA.X()][fixA.Y()] = -1;
blockWorld[fixB.X()][fixB.Y()+1] = a;
}

void Blocks::MoveOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));

if ((fixA.X() == fixB.X()) || (a==b)) return;

blockWorld[fixA.X()][fixA.Y()] = -1;
ReturnToInitialPosition(fixA);

for (unsigned int i = fixB.Y()+1; i < blockWorld[fixB.X()].size(); i++)
if (blockWorld[fixB.X()] == -1){
blockWorld[fixB.X()][i] = a;
break;
}
}

void Blocks::PileOnto(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
unsigned int index=1;

if ((fixA.X() == fixB.X()) || (a==b)) return;

ReturnToInitialPosition(fixB);

for (unsigned int i = fixA.Y(); i < blockWorld[fixA.X()].size();i++){
if (blockWorld[fixA.X()][i]==-1) break;
else{
blockWorld[fixB.X()][fixB.Y()+index]= blockWorld[fixA.X()][i];
blockWorld[fixA.X()][i]=-1;
index++;
}
}
}

void Blocks::PileOver(const short a, const short b){
Index fixA(FindBlock(a));
Index fixB(FindBlock(b));
short TopOfStack=0;
unsigned int index = 0;

if ((fixA.X() == fixB.X()) || (a==b)) return;

for(unsigned int i = fixB.Y()+1; i < blockWorld[fixB.X()].size(); i++)
if (blockWorld[fixB.X()][i]==-1){
TopOfStack = i;
break;
}

index = 0;
for (unsigned int i = TopOfStack; i < blockWorld[fixB.X()].size(); i++){
if (blockWorld[fixA.X()][fixA.Y()+index] == -1) break;
else{
blockWorld[fixB.X()][i] = blockWorld[fixA.X()][fixA.Y()+index];
blockWorld[fixA.X()][fixA.Y()+index] = -1;
index++;
}
}
}

short Blocks::NumBlocks (){
return n_blocks;
}

void Blocks::WriteWorld() const{
for(unsigned int i=0; i < blockWorld.size(); i++){
cout << i << ": ";
for(unsigned int j = 0; j < blockWorld[i].size(); j++){
if (blockWorld[i][j] == -1) break;
cout << blockWorld[i][j] << " ";
}
cout << endl;
}
}

int main(){
string cmd1;
string cmd2;
short a;
short b;
short n;
string line;
Blocks blockWorld;

cin >> n;
if ((n>0)&&(n<25)){
blockWorld.Set(n);
while ((cin >> cmd1) && (cmd1 != "quit")){
cin >> a >> cmd2 >> b;
if ((a>=0)&&(b>=0) && (a < blockWorld.NumBlocks()) && (b < blockWorld.NumBlocks())){
if ((cmd1 == "move") && (cmd2 == "onto")) blockWorld.MoveOnto(a,b);
else if ((cmd1 == "move") && (cmd2 == "over")) blockWorld.MoveOver(a,b);
else if ((cmd1 == "pile") && (cmd2 == "onto")) blockWorld.PileOnto(a,b);
else if ((cmd1 == "pile") && (cmd2 == "over")) blockWorld.PileOver(a,b);
}
}
blockWorld.WriteWorld();
}
}
[/cpp]
Thanks,
Miguel Correia Ricardo
E_mail:miguel_ricardo@hotmail.com
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Re: I got Acepted

Post by szymcio2001 »

Your first code is too long to read it for me :-? but I had the similar error in my solution. I wrote then a program that generated a long, random inputs and I were running my program with those inputs. In this way I found the input that my program didn't solve (it gave a runtime error). If someone will have similar error in the future, he can do it too. Good luck!
George
New poster
Posts: 8
Joined: Tue Mar 11, 2003 10:29 pm

101 - Why W.A.? - Tested on many excamples

Post by George »

[cpp]#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

int (*bl)[25] = new int[25][25];
int n;

// move 9 onto 1
// InpA = 9
// InpB = 1
// InpC = "move"
// InpP = "onto"
int InpA, InpB;
char *InpC = new char;
char *InpP = new char;

//
void Complete_bl(void);
bool ReadInput(void);
void ProcessInput(void);
void ReturnBlocks(int pile_num, int bl_num);
void AddToPile(int pile_num, int bl_num);
void WriteOutput(void);

void Complete_bl(void)
{
for (int i = 0; i < 25; i++)
for (int j = 0; j < 25; j++)
{
if (j == 0)
{
bl[j] = i;
}
else
bl[j] = -1;
}
}

bool ReadInput(void)
{
scanf ("%s %d %s %d", InpC, &InpA, InpP, &InpB);
if (InpC[0] == 'q')
return false;

return true;
}

void ProcessInput(void)
{
int Apile, Apos, Bpile, Bpos;
int i, j;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if (bl[j] == InpA)
{
Apile = i;
Apos = j;
}
if (bl[j] == InpB)
{
Bpile = i;
Bpos = j;
}
}

if (Apile == Bpile)
return;

if (InpC[0] == 'm')
{ //move
if (InpP[1] == 'n')
{ //move A onto B
ReturnBlocks(Apile, InpA);
ReturnBlocks(Bpile, InpB);
bl[Bpile][Bpos+1] = InpA;
bl[Apile][Apos] = -1;
}
else
{ //move A over B
ReturnBlocks(Apile, InpA);
AddToPile(Bpile, InpA);
bl[Apile][Apos] = -1;
}
}
else
{ //pile
if (InpP[1] == 'n')
{ //pile A onto B
ReturnBlocks(Bpile, InpB);
for (i = Apos; bl[Apile]!=-1; i++)
{
AddToPile(Bpile, bl[Apile]);
bl[Apile] = -1;
}
}
else
{ //pile A over B
for (i = Apos; bl[Apile]!=-1; i++)
{
AddToPile(Bpile, bl[Apile]);
bl[Apile] = -1;
}
}
}
}

void ReturnBlocks(int pile_num, int bl_num)
{
for (int i = n-1; i >= 0; i--)
{
if (bl[pile_num][i] != 1)
{
if (bl[pile_num][i] != bl_num)
{
AddToPile(bl[pile_num][i], bl[pile_num][i]);
bl[pile_num][i] = -1;
}
else
return;
}
}
}

void AddToPile(int pile_num, int bl_num)
{
int i;
for (i = 0; bl[pile_num][i]!=-1 ; i++);
bl[pile_num][i] = bl_num;
}

void WriteOutput(void)
{
for (int i = 0; i < n; i++)
{
printf("%d:", i);
for (int j = 0; bl[i][j]!=-1; j++)
printf(" %d", bl[i][j]);
printf("\n");
}
}

void main(void)
{
scanf ("%d", &n);
Complete_bl();

while (ReadInput())
{
ProcessInput();
}
WriteOutput();
}[/cpp]

What's wrong here? It works fine with many excamples!
Izmunuti
New poster
Posts: 10
Joined: Mon Feb 10, 2003 7:22 am

Post by Izmunuti »

You might want to consider illegal inputs. Think about what your program would do if you added these lines to your input:

Code: Select all

move 0 ontopof 6 
relocate 6 before 3 
Iz
Post Reply

Return to “Volume 1 (100-199)”