Why is my simple recusive method's final return value always off by 1?
Posted
by FrankTheTank
on Stack Overflow
See other posts from Stack Overflow
or by FrankTheTank
Published on 2010-04-29T01:46:04Z
Indexed on
2010/04/29
2:17 UTC
Read the original article
Hit count: 337
I'm attempting to create a text-based version of this game:
http://www.cse.nd.edu/java/SameGame.html
Here is the code I have so far:
#include <iostream>
#include <vector>
#include <ctime>
class Clickomania
{
public:
Clickomania();
std::vector<std::vector<int> > board;
int move(int, int);
bool isSolved();
void print();
void pushDown();
bool isValid();
};
Clickomania::Clickomania()
: board(12, std::vector<int>(8,0))
{
srand((unsigned)time(0));
for(int i = 0; i < 12; i++)
{
for(int j = 0; j < 8; j++)
{
int color = (rand() % 3) + 1;
board[i][j] = color;
}
}
}
void Clickomania::pushDown()
{
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 12; j++)
{
if (board[j][i] == 0)
{
for(int k = j; k > 0; k--)
{
board[k][i] = board[k-1][i];
}
board[0][i] = 0;
}
}
}
}
int Clickomania::move(int row, int col)
{
bool match = false;
int totalMatches = 0;
if (row > 12 || row < 0 || col > 8 || col < 0)
{
return 0;
}
int currentColor = board[row][col];
board[row][col] = 0;
if ((row + 1) < 12)
{
if (board[row+1][col] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row+1, col);
}
}
if ((row - 1) >= 0)
{
if (board[row-1][col] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row-1, col);
}
}
if ((col + 1) < 8)
{
if (board[row][col+1] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row, col+1);
}
}
if ((col - 1) >= 0)
{
if (board[row][col-1] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row, col-1);
}
}
return totalMatches;
}
void Clickomania::print()
{
for(int i = 0; i < 12; i++)
{
for(int j = 0; j < 8; j++)
{
std::cout << board[i][j];
}
std::cout << "\n";
}
}
int main()
{
Clickomania game;
game.print();
int row;
int col;
std::cout << "Enter row: ";
std::cin >> row;
std::cout << "Enter col: ";
std::cin >> col;
int numDestroyed = game.move(row,col);
game.print();
std::cout << "Destroyed: " << numDestroyed << "\n";
}
The method that is giving me trouble is my "move" method. This method, given a pair of coordinates, should delete all the squares at that coordinate with the same number and likewise with all the squares with the same number connected to it.
If you play the link I gave above you'll see how the deletion works on a click.
int Clickomania::move(int row, int col)
{
bool match = false;
int totalMatches = 0;
if (row > 12 || row < 0 || col > 8 || col < 0)
{
return 0;
}
int currentColor = board[row][col];
board[row][col] = 0;
if ((row + 1) < 12)
{
if (board[row+1][col] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row+1, col);
}
}
if ((row - 1) >= 0)
{
if (board[row-1][col] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row-1, col);
}
}
if ((col + 1) < 8)
{
if (board[row][col+1] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row, col+1);
}
}
if ((col - 1) >= 0)
{
if (board[row][col-1] == currentColor)
{
match = true;
totalMatches++;
totalMatches += move(row, col-1);
}
}
return totalMatches;
}
My move() method above works fine, as in, it will delete the appropriate "blocks" and replace them with zeros. However, the number of destroyed (value returned) is always one off (too small). I believe this is because the first call of move() isn't being counted but I don't know how to differentiate between the first call or subsequent calls in that recursive method.
How can I modify my move() method so it returns the correct number of destroyed blocks?
© Stack Overflow or respective owner