Code:
#include <iostream>
const int ROWS = 5;
const int COLS = 11;
// drives the recursive count function
int matrixCountDriver(char table[ROWS][COLS]);
// recursivly "flood fills" an object to which it is passed the location, returns true if it has filled an object
// false otherwise
bool matrixCounter(int row, int col, char table[ROWS][COLS], bool checkedAlready[ROWS][COLS]);
// tells if a particular position is indeed a valid part of object, will accept out of bounds indexes
bool checkPosition(int row, int col,
char table[ROWS][COLS], bool checkedAlready[ROWS][COLS]);
int main(int argc, char *argv[])
{
int X = 'X';
char table1[ROWS][COLS] = {
{ 0,X,X,X,0,X,X,X,X,X,X } ,
{ X,X,0,X,X,X,0,X,X,X,0 } ,
{ X,0,0,0,0,0,0,0,0,0,0 } ,
{ 0,0,0,X,0,0,0,0,0,X,X } ,
{ 0,0,0,0,0,0,0,0,0,0,X }
};
char table2[ROWS][COLS] = {
{ 0,X,X,X,0,X,X,X,X,X,X } ,
{ X,X,0,X,X,X,0,X,X,X,0 } ,
{ X,0,0,X,0,0,0,0,0,0,0 } ,
{ 0,0,0,X,X,X,X,X,X,X,X } ,
{ 0,0,0,0,0,0,0,0,0,0,X }
};
char table3[ROWS][COLS] = {
{ 0,0,X,X,0,X,X,X,X,X,X } ,
{ X,0,0,X,X,0,0,X,X,X,0 } ,
{ X,X,0,0,0,0,0,0,0,0,0 } ,
{ 0,0,0,X,0,0,X,0,0,X,X } ,
{ 0,X,0,0,0,0,0,0,0,0,X }
};
std::cout << matrixCountDriver(table1) << endl;
std::cout << matrixCountDriver(table2) << endl;
std::cout << matrixCountDriver(table3) << endl;
char wait; cin >> wait;
}
bool checkPosition(int row, int col,
char table[ROWS][COLS], bool checkedAlready[ROWS][COLS]) {
if (row < 0 || row >= ROWS || col < 0 || col >= COLS) return false; // out of bounds indexes
if (table[row][col] == 'X' && !checkedAlready[row][col]) return true;
return false;
}
bool matrixCounter(int row, int col, char table[ROWS][COLS], bool checkedAlready[ROWS][COLS]) {
if (checkPosition(row, col, table, checkedAlready)) { // this is an row,col has an x and it has not yet been discovered yet
checkedAlready[row][col] = true;
matrixCounter(row + 1, col, table, checkedAlready);
matrixCounter(row - 1, col, table, checkedAlready);
matrixCounter(row, col + 1, table, checkedAlready);
matrixCounter(row, col - 1, table, checkedAlready);
return true;
}
else return false; // this has either already been checked, or is not an 'x'
}
int matrixCountDriver(char table[ROWS][COLS]) {
bool checkedAlready[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
checkedAlready[i][j] = false;
}
}
int count = 0;
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (matrixCounter(i, j, table, checkedAlready)) count++;
}
}
return count;
}