recursive matrix traversal

i am trying to write a function to find the number of objects in a matrix of characters, where an object is defined as an group of adjacent 'X's (not diagonal) not separated by a '0'

ex)
0XXX0XXXXXX
XX0XXX0XXX0
X0000000000
000X00000XX
0000000000X

has 3 objects: one at the top because all of them are connected, the three at the bottom right, and the single X in the middle.

I can write it iteratively, but it is complicated and i would like to have a recursive function that is easier to see.

i would imagine thaat the function would have four recursive calls in it to check left, up, right, and down. any help is appreciated. Thanks!

Heh, this is very similar to what we are now doing in data structures with graph traversal. I was gonna try to write a psuedocode algorithm for it... but I just broke down and slapped this puppy out in 25 minutes ;), it compiles and gives predicted results with Dev-C++.

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;
}

---

I did something similar in a data structures course.
Sorry the code isn't the most explanatory.
It finds blobs in a grid. But I believe they can be diagonally attached (that's easy to fix though).

a link to the other thread
http://www.cprogramming.com/cboard/s...ighlight=blobs

maybe it'll help a little, uses recursion.