101 - The Blocks Problem

[kunami]

I've also got a compiler error, but it's more bizarre

05345248_24.c: In function `int main()':
05345248_24.c:230: Internal compiler error in `const_hash', at varasm.c:2373

It compiles fine with g++ -Wall (GCC 4.1.2 on Ubuntu) over here.
So, should I post a bug report?

Actual code follows:

Code: Select all

#include <iostream>
#include <stack>

class BlockWorld
{
private:
	int numSpaces;
	std::stack<int> *spaces;
	int *blockPosition;

	void AllocateArrays();
	bool IllegalOperation(int src, int dest) const;
	void UnpileOver(int block);
	void MoveBlock(int src, int dest);
	void MovePile(int src, int dest);
public:
	BlockWorld(int newNumSpaces);	// default constructor
	BlockWorld(const BlockWorld &other);	// copy constructor
	~BlockWorld();					// destructor

	void MoveOnto(int src, int dest);
	void MoveOver(int src, int dest);
	void PileOnto(int src, int dest);
	void PileOver(int src, int dest);

	void PrintOut(std::ostream &target = std::cout) const;
};



void BlockWorld::AllocateArrays()
{
	spaces = new std::stack<int>[numSpaces];
	blockPosition = new int[numSpaces];
}



BlockWorld::BlockWorld(int newNumSpaces):numSpaces(newNumSpaces)
{
	AllocateArrays();
	for(int ii = 0; ii < numSpaces; ii++)
	{
		blockPosition[ii] = ii;
		spaces[ii].push(ii);
	}
}



BlockWorld::BlockWorld(const BlockWorld &other):numSpaces(other.numSpaces)
{
	AllocateArrays();
	for(int ii = 0; ii < numSpaces; ii++)
	{
		spaces[ii] = other.spaces[ii];
		blockPosition[ii] = other.blockPosition[ii];
	}
}



BlockWorld::~BlockWorld()
{
	delete[] spaces;
	delete[] blockPosition;
}



bool BlockWorld::IllegalOperation(int src, int dest) const
{
	if(src == dest || blockPosition[src] == blockPosition[dest])
		return true;

	return false;
}



void BlockWorld::UnpileOver(int block)
{
	while(spaces[blockPosition[block]].top() != block)
	{
		int newBlock = spaces[blockPosition[block]].top();
		spaces[blockPosition[block]].pop();
		spaces[newBlock].push(newBlock);
		blockPosition[newBlock] = newBlock;
	}
}



void BlockWorld::MoveBlock(int src, int dest)
{
	spaces[blockPosition[src]].pop();
	blockPosition[src] = blockPosition[dest];
	spaces[blockPosition[dest]].push(src);
}



void BlockWorld::MovePile(int src, int dest)
{
	std::stack<int> temp;

	while(spaces[blockPosition[src]].top() != src)
	{
		temp.push(spaces[blockPosition[src]].top());
		spaces[blockPosition[src]].pop();
	}

	temp.push(spaces[blockPosition[src]].top());
	spaces[blockPosition[src]].pop();

	while(!temp.empty())
	{
		int block = temp.top();
		temp.pop();
		blockPosition[block] = blockPosition[dest];
		spaces[blockPosition[dest]].push(block);
	}
}



void BlockWorld::MoveOnto(int src, int dest)
{
	if(IllegalOperation(src, dest))
		return;
	
	UnpileOver(src);
	UnpileOver(dest);

	MoveBlock(src, dest);	
}



void BlockWorld::MoveOver(int src, int dest)
{
	if(IllegalOperation(src, dest))
		return;

	UnpileOver(src);

	MoveBlock(src, dest);
}



void BlockWorld::PileOnto(int src, int dest)
{
	if(IllegalOperation(src, dest))
		return;

	UnpileOver(dest);

	MovePile(src, dest);
}



void BlockWorld::PileOver(int src, int dest)
{
	if(IllegalOperation(src, dest))
		return;
	
	MovePile(src, dest);
}



void BlockWorld::PrintOut(std::ostream &target) const
{
	std::stack<int> temp;
	for(int ii = 0; ii < numSpaces; ii++)
	{
		target << ii << ": ";
		while(!spaces[ii].empty())
		{
			temp.push(spaces[ii].top());
			spaces[ii].pop();
		}

		while(!temp.empty())
		{
			int block = temp.top();
			temp.pop();
			target << block << (temp.empty() ? "" : " ");
			spaces[ii].push(block);
		}

		target << std::endl;
	}
}



int main()
{
	int numBlocks;
	std::cin >> numBlocks;

	BlockWorld bw(numBlocks);
	void (BlockWorld::*moveFunction[2][2])(int, int) = 
	{
		{ &BlockWorld::MoveOnto, &BlockWorld::MoveOver },
		{ &BlockWorld::PileOnto, &BlockWorld::PileOver }
	};

	while(true)
	{		
		std::string s1, s2;
		int ii, jj, fx, fy;
		std::cin >> s1;
		if(s1 == "quit" || !std::cin)
			break;
		std::cin >> ii >> s2 >> jj;
		if(!std::cin)
			break;
		
		s1 == "move" ? fx = 0 : fx = 1;
		s2 == "onto" ? fy = 0 : fy = 1;

		(bw.*moveFunction[fx][fy])(ii, jj);		
	}

	bw.PrintOut();

	return 0;
}

[kunami]

Apparently the Judge's version of GCC didn't like the member function pointers. It compiles now, I just get a Presentation Error I've got to figure out.

[cassio]

Update: Nevermind. I managed to solve my problem and got accepted.

Ok, I cannot seem to get past the Invalid memory reference error. (signal 11 (SIGSEGV)).

I have tested the code against various inputs in the board including this one and got the same results as other people, for example:

21
move 2 onto 1
move 3 onto 2
move 4 onto 3
move 5 over 1
pile 1 over 10
move 9 over 8
move 11 over 8
pile 3 over 8
pile 8 over 3
move 20 over 19
pile 19 over 18
pile 18 onto 15
move 15 over 3
pile 20 onto 19
pile 19 onto 18
pile 18 over 17
quit

answer should be

0: 0
1:
2:
3:
4:
5:
6: 6
7: 7
8: 8 9 11 3 4 5 15
9:
10: 10 1 2
11:
12: 12
13: 13
14: 14
15:
16: 16
17: 17 18 19 20
18:
19:
20:

The code doesnt segfault on my test cases.

I'm attaching the version i sent to the judge. I have another version with some debugging information turned on (it will show a table with all the pointers after each operation is executed) so it's easier to see what's going on.

I hope someone can help me understand why it's getting signal 11 or at least provide me with input that breaks it.

Thank you!

Code sent to judge:

Code: Select all

code removed.

[cryu]

I tested my code with many test data. My program made the correct result. But i got the WA from ACM judge. Someone could help me find the bugs in my program? Thanks!

-----------------------------------------------------------------------------

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define N 25
#define input cin
//string filename = "Q101.txt";
//ifstream input(filename.c_str(), ios::in);

struct Index
{
int blocks;
int level;
};


int blocks [N][N];
int num;
string command[2];
int ia, ib;
string options[4] = {"move", "pile", "onto", "over"};

void initial()
{
for(int i = 0; i < num; i++)
{
blocks[0] = i;
for(int j = 1; j < N; j++)
{
blocks[j] = -1;
}
}
}

Index find(int a)
{
Index value;
for(int i = 0; i < num; i++)
{
for(int j = 0; j < num; j++)
{
if(blocks[j] == -1)//end of the i th blocks
break;

if(blocks[j] == a)//find a
{
value.blocks = i;
value.level = j;
return value;
}
}
}

return value;
}
void pile(int a, int b, Index indexA, Index indexB)
{
while(blocks[indexB.blocks][indexB.level] != -1)
{
indexB.level++;
}

while(blocks[indexA.blocks][indexA.level] != -1)
{
blocks[indexB.blocks][indexB.level++] = blocks[indexA.blocks][indexA.level];
blocks[indexA.blocks][indexA.level++] = -1;
}
}

void move(int a, int b, Index indexA, Index indexB)
{
while(blocks[indexB.blocks][indexB.level] != -1)
{
indexB.level++;
}

blocks[indexB.blocks][indexB.level] = blocks[indexA.blocks][indexA.level];
blocks[indexA.blocks][indexA.level] = -1;
}

void clear(int a, Index indexA)
{
int j = indexA.level+1;

while(blocks[indexA.blocks][j] != -1)
{
blocks[ blocks[indexA.blocks][j] ][0] = blocks[indexA.blocks][j];
blocks[indexA.blocks][j] = -1;
j++;
}
}

void move_onto(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(a, indexOfA);
clear(b, indexOfB);
move(a, b, indexOfA, indexOfB);
}

void move_over(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(a, indexOfA);
move(a, b, indexOfA, indexOfB);
}

void pile_onto(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(b, indexOfB);
pile(a, b, indexOfA, indexOfB);
}

void pile_over(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

pile(a, b, indexOfA, indexOfB);
}

void Q101()
{
if(ia < 0 || ia >= num || ib < 0 || ib >= num )
return;

if(!command[0].compare("move"))
{
if(!command[1].compare("onto"))
{
move_onto(ia,ib);
//cout<< "move+onto";
}
else if(!command[1].compare("over"))
{
move_over(ia,ib);
//cout<< "move+over";
}
}
else if(!command[0].compare("pile"))
{
if(!command[1].compare("onto"))
{
pile_onto(ia,ib);
//cout<< "pile+onto";
}
else if(!command[1].compare("over"))
{
pile_over(ia,ib);
//cout<< "pile+over";
}
}
}

void read()
{
input >> command[0];
}

void read2()
{
input >> ia >> command[1] >> ib;
}
void print()
{
for(int i = 0; i < num; i++)
{
cout<< i << ':';
for(int j = 0; j < num; j++)
{
if(blocks[j] == -1)//end of the i th blocks
break;

cout<< ' ' << blocks[j];
}
cout<<endl;
}
}

int main()
{
while(!input.eof())
{
input>>num;
initial();
while(1)
{
read();
if(!command[0].compare("quit"))
break;
read2();
Q101();
//print();
//system("pause");
//cout<<endl;
}
print();
//system("pause");
}
//system("pause");
}

[helloneo]

Don't create a new thread if there is one already..
Use old threads..

http://online-judge.uva.es/board/viewtopic.php?t=4019

[cryu]

Help!! WA(101)

I tested my code with many test data. My program made the correct result. But i got the WA from ACM judge. Someone could help me find the bugs in my program? Thanks!

-----------------------------------------------------------------------------

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define N 25
#define input cin
//string filename = "Q101.txt";
//ifstream input(filename.c_str(), ios::in);

struct Index
{
int blocks;
int level;
};


int blocks [N][N];
int num;
string command[2];
int ia, ib;
string options[4] = {"move", "pile", "onto", "over"};

void initial()
{
for(int i = 0; i < num; i++)
{
blocks[0] = i;
for(int j = 1; j < N; j++)
{
blocks[j] = -1;
}
}
}

Index find(int a)
{
Index value;
for(int i = 0; i < num; i++)
{
for(int j = 0; j < num; j++)
{
if(blocks[j] == -1)//end of the i th blocks
break;

if(blocks[j] == a)//find a
{
value.blocks = i;
value.level = j;
return value;
}
}
}

return value;
}
void pile(int a, int b, Index indexA, Index indexB)
{
while(blocks[indexB.blocks][indexB.level] != -1)
{
indexB.level++;
}

while(blocks[indexA.blocks][indexA.level] != -1)
{
blocks[indexB.blocks][indexB.level++] = blocks[indexA.blocks][indexA.level];
blocks[indexA.blocks][indexA.level++] = -1;
}
}

void move(int a, int b, Index indexA, Index indexB)
{
while(blocks[indexB.blocks][indexB.level] != -1)
{
indexB.level++;
}

blocks[indexB.blocks][indexB.level] = blocks[indexA.blocks][indexA.level];
blocks[indexA.blocks][indexA.level] = -1;
}

void clear(int a, Index indexA)
{
int j = indexA.level+1;

while(blocks[indexA.blocks][j] != -1)
{
blocks[ blocks[indexA.blocks][j] ][0] = blocks[indexA.blocks][j];
blocks[indexA.blocks][j] = -1;
j++;
}
}

void move_onto(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(a, indexOfA);
clear(b, indexOfB);
move(a, b, indexOfA, indexOfB);
}

void move_over(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(a, indexOfA);
move(a, b, indexOfA, indexOfB);
}

void pile_onto(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

clear(b, indexOfB);
pile(a, b, indexOfA, indexOfB);
}

void pile_over(int a, int b)
{
Index indexOfA = find(a);
Index indexOfB = find(b);

if(indexOfA.blocks == indexOfB.blocks)
return;

pile(a, b, indexOfA, indexOfB);
}

void Q101()
{
if(ia < 0 || ia >= num || ib < 0 || ib >= num )
return;

if(!command[0].compare("move"))
{
if(!command[1].compare("onto"))
{
move_onto(ia,ib);
//cout<< "move+onto";
}
else if(!command[1].compare("over"))
{
move_over(ia,ib);
//cout<< "move+over";
}
}
else if(!command[0].compare("pile"))
{
if(!command[1].compare("onto"))
{
pile_onto(ia,ib);
//cout<< "pile+onto";
}
else if(!command[1].compare("over"))
{
pile_over(ia,ib);
//cout<< "pile+over";
}
}
}

void read()
{
input >> command[0];
}

void read2()
{
input >> ia >> command[1] >> ib;
}
void print()
{
for(int i = 0; i < num; i++)
{
cout<< i << ':';
for(int j = 0; j < num; j++)
{
if(blocks[j] == -1)//end of the i th blocks
break;

cout<< ' ' << blocks[j];
}
cout<<endl;
}
}

int main()
{
while(!input.eof())
{
input>>num;
initial();
while(1)
{
read();
if(!command[0].compare("quit"))
break;
read2();
Q101();
//print();
//system("pause");
//cout<<endl;
}
print();
//system("pause");
}
//system("pause");
}

[mikehammer]

i know it is exhausting, but could someone have look at my code. It seems to use an "Invalid memory reference".

#include <iostream>
#include <stdio.h>
#include <list>
#include <vector>

int size;
using namespace std;

vector<list<int>::iterator> positions(0) ; // a pointer to each blocks position
vector<list<int> > lists(0) ; // the lists of blocks
vector<int> where(0) ; // the number of the list an element is contained

typedef struct
{
int& next;
int value;
} listel;

typedef struct
{
listel& begin;
listel& end;
} Liste;



void init() //initialising
{
for (int i=0;i<size; i++)
{
lists.push_front(i);
positions=lists.begin();
where=i;
}
}

void output() //output procedure
{
list<int>::iterator it;
for (int i=0; i<size;i++)
{
cout << i << ":";
it=lists.begin();
while (it!=lists.end())
{
cout <<" " << *it;
it++;
}
cout << "\n";
//cout << "--" << i << " is in " <<where << "\n";
}
}


void moveonto(int a,int b)
{
int wherea,whereb,lastel;

wherea=where[a];


while (--lists[wherea].end() != positions[a]) //clear above a
{
lastel=lists[wherea].back();
lists[lastel].push_back(lastel);
positions[lastel]=--lists[lastel].end();
lists[wherea].pop_back();
where[lastel]=lastel;
}

whereb=where;
while (--lists[whereb].end() != positions) //clear above b;
{
lastel=lists[whereb].back();
lists[lastel].push_back(lastel);
positions[lastel]=--lists[lastel].end();
lists[whereb].pop_back();
where[lastel]=lastel;
}

wherea=where[a];
where[a]=where; // move a
lists[wherea].pop_back();
lists[whereb].push_back(a);
positions[a]=--lists[whereb].end();

}


void moveover(int a,int b)
{
int wherea,lastel;

wherea=where[a];
while (--lists[wherea].end() != positions[a]) //clear above a
{
lastel=lists[wherea].back();
lists[lastel].push_back(lastel);
positions[lastel]=--lists[lastel].end();
lists[wherea].pop_back();
where[lastel]=lastel;
}


where[a]=where; //move a
lists[wherea].pop_back();
lists[where].push_back(a);
positions[a]=--lists[where].end();
}

void pileonto(int a,int b)
{
int wherea,whereb,lastel;

whereb=where;
wherea=where[a];
while (--lists[whereb].end() != positions) //clear above b
{
lastel=lists[whereb].back();
lists[lastel].push_back(lastel);
positions[lastel]=--lists[lastel].end();
lists[whereb].pop_back();
where[lastel]=lastel;
}

list<int>::iterator temp,temp1;
temp = positions[a];

while (temp!=lists[wherea].end()) // move the stack above a over b
{
temp1=temp;
temp1++;
lists[whereb].push_back(*temp);
positions[*temp]=--lists[whereb].end();
lists[wherea].erase(temp);
where[*temp]=whereb;
temp=temp1;
}

}


void pileover(int a,int b)
{
int wherea,whereb;

wherea=where[a];
whereb=where;

if (wherea!=whereb) {
list<int>::iterator temp,temp1;
temp=positions[a];


while (temp!=lists[wherea].end()) //move the stack above a over b
{
temp1=temp;
temp1++;
lists[whereb].push_back(*temp);
positions[*temp]=--lists[whereb].end();
lists[wherea].erase(temp);
where[*temp]=whereb;
temp=temp1;
}
}


}


int main() //main program
{
int a,b;
char s1[5],s2[5];

cin >> size;
positions.resize(size);
lists.resize(size);
where.resize(size);
init();
cin >> s1;
while (strcmp(s1,"quit")!=0)
{
cin >> a >> s2 >> b;
if (strcmp(s1,"move")==0){
if (strcmp(s2,"onto")==0) {moveonto(a,b);}
else {moveover(a,b);}
}
else {
if (strcmp(s2,"onto")==0) {pileonto(a,b);}
else {pileover(a,b);}
}
cin >> s1;
}
}

[Phocasia]

I compile on my PC are correctly ,but I getting Runtime Error Signal 11

Code: Select all

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

typedef struct block_t {
	short name;
	struct block_t *next;
}BLOCK;

void clearBlock(BLOCK *[]);

int main(void) {
	char str[5] ,mode ,flag;
	short n ,a ,b ,i ,j ,tA ,tB ,fA ,fB;
	BLOCK **ptA ,**ptB ,**tmp ,*block[25]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

	for(i=0;i<25;++i) {
		block[i] = (BLOCK *)malloc(sizeof(BLOCK));
		block[i]->name = i;
		block[i]->next = NULL;
	}
	
	while(scanf(" %hd" ,&n)!=EOF) {
		
		while(scanf(" %s" ,str)!=EOF && str[0]!='q') {
			scanf(" %hd" ,&a);
			mode = str[0];
			scanf(" %s %hd" ,str ,&b);

			if(a!=b && 0<=a && a<n && 0<=b && b<n) {
				flag = 0;
				for(i=0 ,ptA=NULL ,ptB=NULL; !ptA || !ptB ;++i) {
					for(tmp=&block[i] ,j=0; *tmp ;tmp=&(*tmp)->next ,j++) {
						if((*tmp)->name == a) {
							ptA = tmp;
							tA = i;
							fA = j;
						}
						if((*tmp)->name == b) {
							ptB = &(*tmp)->next;
							tB = i;
							fB = j;
							flag = 1;
						}
					}
					if(ptB && str[1]=='v' && flag) {
						ptB = tmp;
						flag = 0;
					}
				}
				if(!(mode=='p' && tA==tB && fA<fB)) {
					if(mode=='m') {
						while(*ptB) {
							block[(*ptB)->name] = *ptB;
							tmp = &block[(*ptB)->name];
							*ptB = (*ptB)->next;
							(*tmp)->next = NULL;
						}
						while((*ptA)->next) {
							block[(*ptA)->next->name] = (*ptA)->next;
							tmp = &block[(*ptA)->next->name];
							(*ptA)->next = (*ptA)->next->next;
							(*tmp)->next = NULL;
						}
					} else if(*ptB) {
						block[(*ptB)->name] = *ptB;
						*ptB = NULL;
					}
					*ptB = *ptA;
					*ptA = NULL;
				}
			}
		}
		for(i=0;i<n;++i) {
			printf("%d:" ,i);
			for(tmp=&block[i]; *tmp ;tmp=&(*tmp)->next) {
				printf(" %d" ,(*tmp)->name);
			}
			printf("\n");
		}
		for(i=0;i<25;++i) {
			if(block[i]) {
				for(;block[i]->next;) {
					block[block[i]->next->name] = block[i]->next;
					tmp = &block[block[i]->next->name];
					block[i]->next = block[i]->next->next;
					(*tmp)->next = NULL;
				}
			}
		}
	}
	clearBlock(block);
	return 0;
}

void clearBlock(BLOCK *block[]) {
	short i;
	BLOCK *tmp;
	for(i=0;i<25;++i) {
		while(block[i]) {
			tmp = block[i];
			block[i] = block[i]->next;
			free(tmp);
		}
	}
}

Anybody plz tell me where my code is wrong.

[Jan]

Search the board first. Don't open a new thread if there is one already.

[Caio Abrantes]

Here is my code if anyone can find the mistake i would be greatful:

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

int **tabuleiroBlocos;
const char *stdComandos[] = { "moveonto", "moveover", "pileonto", "pileover", "quit" };

void aloca( int n );
void inicializa( int n );
void leComando( char *comando, int *aPtr, int *bPtr );
void search( int n, int bloco, int *linha, int *coluna );
void output( int n );

void moveonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void moveover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void pileonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void pileover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );

int main( void )
{
int i, j;
int n = 0;
char comando[10];
int a, b;
int alinha, acoluna;
int blinha, bcoluna;
void (*f[4])( int , int , int , int , int , int , int ) = { moveonto, moveover, pileonto, pileover };

while ( n <= 0 || n >= 25 ) {

scanf( "%d", &n );

getchar();

}

if ( n != 1 ) {

aloca( n );


inicializa( n );

for (;;) {

leComando( comando, &a, &b );

if ( strcmp( comando, "quit" ) == 0 )

break;

if ( a == b )

continue;

search( n, a, &alinha, &acoluna );

search( n, b, &blinha, &bcoluna );

if ( alinha == blinha )

continue;

for ( i = 0; i < 4; i++ )

if ( strcmp( comando, stdComandos ) == 0 )

(*f)( n, a, alinha, acoluna, b, blinha, bcoluna );

}

output( n );

}
else {

leComando( comando, &a, &b );

while ( strcmp( comando, "quit" ) != 0 ) {

leComando( comando, &a, &b );

}

printf( "0: 0\n" );

}

return 0;

}

void aloca( int n )
{
int i;

tabuleiroBlocos = ( int ** )malloc( n * sizeof( int * ) );

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

tabuleiroBlocos = ( int * )malloc( n * sizeof( int ) );

return;

}

void inicializa( int n )
{
int i, j;

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

tabuleiroBlocos[0] = i;

for ( j = 1; j < n; j++ )

tabuleiroBlocos[j] = -1;

}

return;

}

void leComando( char *comando, int *aPtr, int *bPtr )
{
int i, j;
char comandoAuxiliar[20];
char *aAuxiliar;
char *bAuxiliar;

gets( comandoAuxiliar );

for ( i = 0, j = 0; i < strlen( comandoAuxiliar ); i++ ) {

if ( isalpha( comandoAuxiliar ) )

comando[j++] = comandoAuxiliar;

else

continue;

}

comando[j] = '\0';

if ( strcmp( comando, "quit" ) == 0 )

return;

strtok( comandoAuxiliar, " " );

aAuxiliar = strtok( NULL, " " );

*aPtr = atoi( aAuxiliar );

strtok( NULL, " " );

bAuxiliar = strtok( NULL, " " );

*bPtr = atoi( bAuxiliar );

return;

}

void search( int n, int bloco, int *linha, int *coluna )
{
int i, j;

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

for ( j = 0; j < n; j++ ) {

if ( tabuleiroBlocos[j] == bloco ) {

*linha = i;
*coluna = j;
}

}

}

return;

}

void output( int n )
{
int i, j;

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

printf( "%d:", i );

for ( j = 0; j < n; j++ ) {

if ( tabuleiroBlocos[j] != -1 )

printf( " %d", tabuleiroBlocos[j] );

}

printf( "\n" );

}

return;

}

void moveonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[alinha][i]][0] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;
}
else

break;

}

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[blinha][i]][0] = tabuleiroBlocos[blinha][i];
tabuleiroBlocos[blinha][i] = -1;
}
else

break;

}

tabuleiroBlocos[blinha][bcoluna + 1] = a;

return;

}

void moveover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[alinha][i]][0] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;
}
else

break;

}

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] == -1 ) {

tabuleiroBlocos[blinha][i] = a;
break;
}
else

continue;

}

return;

}

void pileonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[blinha][i]][0] = tabuleiroBlocos[blinha][i];
tabuleiroBlocos[blinha][i] = -1;
}
else

break;

}

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[blinha][++bcoluna] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;

}
else

break;

}

return;

}

void pileover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

while ( tabuleiroBlocos[blinha][++bcoluna] != -1 );

while ( tabuleiroBlocos[alinha][acoluna] != -1 ) {

tabuleiroBlocos[blinha][bcoluna++] = tabuleiroBlocos[alinha][acoluna];
tabuleiroBlocos[alinha][acoluna++] = -1;

}

return;

}

[Jan]

Search the board first. Don't open a new thread if one exists already.

[Caio Abrantes]

I need some help here. I've done 101, it works perfectly on my computer but when i submit i keep getting WRONG ANSWER! I have already got 16 WRONG ANSWER and I'm almost giving up. If anyone could take a look at my code and tell me what's wrong with it i would be grateful ! Thanks in advance.

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

int **tabuleiroBlocos;
const char *stdComandos[] = { "moveonto", "moveover", "pileonto", "pileover", "quit" };

void aloca( int n );
void inicializa( int n );
void leComando( char *comando, int *aPtr, int *bPtr );
void search( int n, int bloco, int *linha, int *coluna );
void output( int n );

void moveonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void moveover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void pileonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );
void pileover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna );

int main( void )
{
int i, j;
int n = 0;
char comando[10];
int a, b;
int alinha, acoluna;
int blinha, bcoluna;
void (*f[4])( int , int , int , int , int , int , int ) = { moveonto, moveover, pileonto, pileover };

while ( n <= 0 || n >= 25 ) {

scanf( "%d", &n );

getchar();

}

if ( n != 1 ) {

aloca( n );


inicializa( n );

for (;;) {

leComando( comando, &a, &b );

if ( strcmp( comando, "quit" ) == 0 )

break;

if ( a == b )

continue;

search( n, a, &alinha, &acoluna );

search( n, b, &blinha, &bcoluna );

if ( alinha == blinha )

continue;

for ( i = 0; i < 4; i++ )

if ( strcmp( comando, stdComandos ) == 0 )

(*f)( n, a, alinha, acoluna, b, blinha, bcoluna );

}

output( n );

}
else {

leComando( comando, &a, &b );

while ( strcmp( comando, "quit" ) != 0 ) {

leComando( comando, &a, &b );

}

printf( "0: 0\n" );

}

return 0;

}

void aloca( int n )
{
int i;

tabuleiroBlocos = ( int ** )malloc( n * sizeof( int * ) );

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

tabuleiroBlocos = ( int * )malloc( n * sizeof( int ) );

return;

}

void inicializa( int n )
{
int i, j;

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

tabuleiroBlocos[0] = i;

for ( j = 1; j < n; j++ )

tabuleiroBlocos[j] = -1;

}

return;

}

void leComando( char *comando, int *aPtr, int *bPtr )
{
int i, j;
char comandoAuxiliar[20];
char *aAuxiliar;
char *bAuxiliar;

gets( comandoAuxiliar );

for ( i = 0, j = 0; i < strlen( comandoAuxiliar ); i++ ) {

if ( isalpha( comandoAuxiliar ) )

comando[j++] = comandoAuxiliar;

else

continue;

}

comando[j] = '\0';

if ( strcmp( comando, "quit" ) == 0 )

return;

strtok( comandoAuxiliar, " " );

aAuxiliar = strtok( NULL, " " );

*aPtr = atoi( aAuxiliar );

strtok( NULL, " " );

bAuxiliar = strtok( NULL, " " );

*bPtr = atoi( bAuxiliar );

return;

}

void search( int n, int bloco, int *linha, int *coluna )
{
int i, j;

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

for ( j = 0; j < n; j++ ) {

if ( tabuleiroBlocos[j] == bloco ) {

*linha = i;
*coluna = j;
}

}

}

return;

}

void output( int n )
{
int i, j;

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

printf( "%d:", i );

for ( j = 0; j < n; j++ ) {

if ( tabuleiroBlocos[j] != -1 )

printf( " %d", tabuleiroBlocos[j] );

}

printf( "\n" );

}

return;

}

void moveonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[alinha][i]][0] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;
}
else

break;

}

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[blinha][i]][0] = tabuleiroBlocos[blinha][i];
tabuleiroBlocos[blinha][i] = -1;
}
else

break;

}

tabuleiroBlocos[blinha][bcoluna + 1] = a;

return;

}

void moveover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[alinha][i]][0] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;
}
else

break;

}

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] == -1 ) {

tabuleiroBlocos[blinha][i] = a;
break;
}
else

continue;

}

return;

}

void pileonto( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

for ( i = bcoluna + 1; i < n; i++ ) {

if ( tabuleiroBlocos[blinha][i] != -1 ) {

tabuleiroBlocos[tabuleiroBlocos[blinha][i]][0] = tabuleiroBlocos[blinha][i];
tabuleiroBlocos[blinha][i] = -1;
}
else

break;

}

for ( i = acoluna; i < n; i++ ) {

if ( tabuleiroBlocos[alinha][i] != -1 ) {

tabuleiroBlocos[blinha][++bcoluna] = tabuleiroBlocos[alinha][i];
tabuleiroBlocos[alinha][i] = -1;

}
else

break;

}

return;

}

void pileover( int n, int a, int alinha, int acoluna, int b, int blinha, int bcoluna )
{
int i;

while ( tabuleiroBlocos[blinha][++bcoluna] != -1 );

while ( tabuleiroBlocos[alinha][acoluna] != -1 ) {

tabuleiroBlocos[blinha][bcoluna++] = tabuleiroBlocos[alinha][acoluna];
tabuleiroBlocos[alinha][acoluna++] = -1;

}

return;

}

[smilitude]

I feeling sorry for you.. Caio Abrantes, mikehammer and cryu!
and i really fear that no one can help you with it!
i used to got a lot of invalid memory ref in this problem that i throw it away for months and suddenly oneday i found changing just one line gets ac..

all i can do for you is
- re write the whole code taking your time - so that no bug can bother you!
- before writing the code, convince yourself that your steps are ok and you have no confusion!

[misshappy]

I have read the article in the discuusion board about problem 101 and used a lot of sample input,it always outputs right answer.
But when I upload my code,the system always told me run time error(SIGSEGV)
I don't know what mistakes in my code.Could anyone help me out..?
Thanks a lot.
This is my code link:

http://rafb.net/p/4fJa2c60.html



#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#define MAX 1000
using namespace std;
struct blocks{
int content[MAX];
}blk[MAX];
int main()
{
string start,end;
int size,from,to,fromi,fromj,toi,toj,temp=0;
while(cin>>size){
for(int i=0;i<size;i++)
for(int j=0;j<size;j++){
if(j==0)blk.content[0]=i;
else blk.content[j]=-1;
}

while(cin>>start){
if(start=="quit")break;
cin>>from>>end>>to;
if(from==to)continue;
if(start=="move"&&end=="onto"){
fromi=-1,fromj=-2,toi=-3,toj=-4;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++){
if(blk.content[j]==from)fromi=i,fromj=j;
if(blk.content[j]==to)toi=i,toj=j;
if(fromi==toi){goto L1;}
}
for(int j=fromj+1;blk[fromi].content[j]!=-1;j++)
for(int k=0;k<size;k++)
if(blk[blk[fromi].content[j]].content[k]==-1)blk[blk[fromi].content[j]].content[k]=blk[fromi].content[j],blk[fromi].content[j]=-1;
for(int j=toj+1;blk[toi].content[j]!=-1;j++)
for(int k=0;k<size;k++)
if(blk[blk[toi].content[j]].content[k]==-1)blk[blk[toi].content[j]].content[k]=blk[toi].content[j],blk[toi].content[j]=-1;
blk[toi].content[toj+1]=blk[fromi].content[fromj];blk[fromi].content[fromj]=-1;
L1:;
}
else if(start=="move"&&end=="over"){fromi=-1,fromj=-2,toi=-3,toj=-4;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++){
if(blk.content[j]==from)fromi=i,fromj=j;
if(blk.content[j]==to)toi=i,toj=j;
if(fromi==toi){goto L2;}
}
for(int j=fromj+1;blk[fromi].content[j]!=-1;j++)
for(int k=0;k<size;k++)
if(blk[blk[fromi].content[j]].content[k]==-1)blk[blk[fromi].content[j]].content[k]=blk[fromi].content[j],blk[fromi].content[j]=-1;
for(int j=toj+1;j<size;j++)
if(blk[toi].content[j]==-1){
blk[toi].content[j]=blk[fromi].content[fromj];blk[fromi].content[fromj]=-1;break;
}
L2:;

}
else if(start=="pile"&&end=="onto"){fromi=-1,fromj=-2,toi=-3,toj=-4;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++){
if(blk.content[j]==from)fromi=i,fromj=j;
if(blk.content[j]==to)toi=i,toj=j;
if(fromi==toi){goto L3;}
}
for(int j=toj+1;blk[toi].content[j]!=-1;j++)
for(int k=0;k<size;k++)
if(blk[blk[toi].content[j]].content[k]==-1)blk[blk[toi].content[j]].content[k]=blk[toi].content[j],blk[toi].content[j]=-1;
temp=toj+1;

for(int jj=fromj;jj<size;jj++){
if(blk[fromi].content[jj]!=-1)
blk[toi].content[temp]=blk[fromi].content[jj],blk[fromi].content[jj]=-1,temp++;
}
L3:;
}
else if(start=="pile"&&end=="over"){fromi=-1,fromj=-2,toi=-3,toj=-4;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++){
if(blk.content[j]==from)fromi=i,fromj=j;
if(blk.content[j]==to)toi=i,toj=j;
if(fromi==toi){goto L4;}
}
for(int j=toj+1;j<size;j++){
if(blk[toi].content[j]==-1)temp=j;
break;
}
for(int jj=fromj;jj<size;jj++)
if(blk[fromi].content[jj]!=-1)
blk[toi].content[temp++]=blk[fromi].content[jj],blk[fromi].content[jj]=-1;
L4:;
}
}
for(int i=0;i<size;i++){
cout<<i<<":";
for(int j=0;j<size;j++)
if(blk[i].content[j]!=-1)cout<<" "<<blk[i].content[j];
cout<<endl;
}
}
system("pause");
}

[Jan]

Dont open a new thread if there is one already.