I don't know what standard protocol is in this newsgroup. Am I allowed to
post code and ask for help? I hope so.. :)
Here's my problem: I am trying problem 127 of the valladolid online
contests (http://online-judge.uva.es/p/v1/127.html). The program I wrote
seems to work fine, but it takes way too much memory to run. I am not that
good at programming C++, unfortunately, so I can't seem to find my memory
leak. As far as I can tell, I am deallocating every bit of memory I am
allocating. If someone can skim through my code to help I'd be forever
grateful. It is not that long....
I think I am doing everything correctly.
Thanks to anyone who can help!!
CODE:
#include <iostream>
// Pile class .. simple STACK implementation
class Pile {
private:
int ncards;
char **cards; // array of pointers
public:
Pile() {
ncards = 0;
cards = new char * [52]; // allocate space for 52 pointers
}
~Pile() {
// deallocate all cards in pile
for(int i = 0; i < ncards; i++) delete [] cards[i];
delete [] cards; // deallocate pointers
}
void push(char *card) {
// create a new char array & copy values
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];
ncards++;
}
void pop() {
if(ncards > 0) {
delete [] cards[ncards-1]; // deallocate top card
ncards--;
}
}
char* top() {
// create a new char array, copy values and return it
char *p = new char [2];
p[0] = cards[ncards-1][0];
p[1] = cards[ncards-1][1];
return p;
}
bool isEmpty()
{return (ncards == 0);}
int size()
{return ncards;}
};
int npiles;
Pile **piles; // array of pointers to piles
inline void remove(int pos) {
Pile *p = piles[pos]; // save pointer
// shuffle remaining piles
for(int i = pos; i < npiles-1; i++) piles[i] = piles[i+1];
delete p; // deallocate empty pile
npiles--;
}
bool makeMove() { // compares cards, moves like cards, deallocates empty
piles
for(int i = 1; i < npiles; i++) {
char *cardA = piles[i]->top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff]->top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff]->push(cardA);
piles[i]->pop();
if(piles[i]->isEmpty()) remove(i);
return true;
}
diff -= 2;
}
}
return false;
}
using namespace std;
int main() {
char card[2];
while(cin >> card) {
if(card[0] == '#') return 0;
npiles = 0;
piles = new Pile * [52]; // allocate space for 52 pointers
for(int i = 0; i < 52; i++) piles[i] = new Pile(); // allocate 52
piles
piles[npiles++]->push(card);
for(int i = 1; i < 52; i++) {
cin >> card;
piles[npiles++]->push(card);
}
while(makeMove());
cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles[i]->size();
cout << endl;
// finally deallocate all piles, as well as pointers to them.
for(int i = 0; i < npiles; i++) delete piles[i];
delete [] piles;
}
return 0;
}
SAMPLE INPUT:
QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C
6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C
5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD
KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS
KS
#
