Thread: recursive matrix traversal

  1. #1
    Unregistered
    Guest

    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!

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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;
    }
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Fingerstyle Guitarist taylorguitarman's Avatar
    Join Date
    Aug 2001
    Posts
    564
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  3. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM