# recursive matrix traversal

• 11-12-2001
Unregistered
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!
• 11-12-2001
SilentStrike
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; }```
• 11-12-2001
taylorguitarman
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).