How to label groups within a 2D array using recursion?

user_12381195 0
Viewed 134

I need to write a a method in my code that can take a two dimensional array and return how many different groups there are within the array. A group is defined as, "all cells connected directly to other cells in the up/down/left/right (not diagonal) directions" where a cell in the array would be represented by an asterisk. I need to write a method that iterates through the entire array that also calls a recursive method that changes every asterisk into a letter that is unique to that group. For example this is a sample input:

char image[][] = {
        {'*','*',' ',' ',' ',' ',' ',' ','*',' '},
        {' ','*',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ',' ',' ',' ','*','*',' ',' '},
        {' ','*',' ',' ','*','*','*',' ',' ',' '},
        {' ','*','*',' ','*',' ','*',' ','*',' '},
        {' ','*','*',' ','*','*','*','*','*','*'},
        {' ',' ',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ',' ',' ',' ',' ',' ','*',' '},
        {' ',' ',' ','*','*','*',' ',' ','*',' '},
        {' ',' ',' ',' ',' ','*',' ',' ','*',' '}};

and the output would be something like this:

    aa      b 
     a      b 
          cc  
     d  ccc   
     dd c c c 
     dd cccccc
            c 
            c 
       eee  c 
         e  c

I mostly need help with the method that iterates through the given image because I don't know how to make the code distinguish between the groups.

multidimensional-array recursion arrays java
2 Answers

Your concept should be like this.

checkField (x, y, char)
  x,y is out of bounds; return;

  if current field has asterix do
     current field = char; // Prevents new checks!
     checkField (x+1, y, char); // right field
     checkField (x+-1,y, char); //l left field 
     // top and bottem field.
  else do
    // Advance to next Field; Next field has to be in bounds. At the end of the line you have to go to the next line;
    checkField( .., ..., char++)
end;

The first call would be checkField (0, 0 , 'a');

You need to create a new array of chars. This would be an instance variable.

You could model the x, y matrix as array. Where x mod y is a line. This would make advanceing easier. But less intuitiv.

Try to implement the pseudocode and feel free to update you question in detail.

user_35581330

You need two methods. one to iterate through the given image, and the other draw the asterisk at the point (i, j) with the given name.

Iterating through the given image is so simple

public char[][] iterateThrough(char[][] image, int row, int column) {
    // this is the result.
    char[][] out = new char[][row];
    // fill the result with '\0'
    for (int i = 0; i < row; ++i) {
        out[i] = new char[column];
        for (int j = 0; j < column; ++j) {
            out[i][j] = '\0';
        }
    }
    char name = 'a';
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < column; ++j) {
            // The key is here. You should check the point at (i, j).
            // And if it belongs to a unfound asterisk, add the whole to result.
            // if it belongs to a found asterisk, ignore it.
            char p = image[i][j];
            char r = result[i][j];
            if (p == '*') { // The point belongs to a asterisk
                if (r == '\0') { The asterisk has not been drawn.
                    // draw it.
                    drawAsterisk(image, result, i, j, name++, row, column);
                }
            }
        }
    }
    return out;
}

Now this is how to draw the asterisk

public void drawAsterisk(char[][] image, char[][] result, int i, int j, char name, int row, int column) {
    // draw at point (i, j) if it belongs to a asterisk
    if (image[i][j] == '*') {
        result[i][j] = name;
        // draw right
        if (i + 1 < row) {
            drawAsterisk(image, result, i + 1, j, name, row, column);
        }
        // draw left
        if (i - 1 >= 0) {
            drawAsterisk(image, result, i - 1, j, name, row, column);
        }
        // draw bottom
        if (j + 1 < column) {
            drawAsterisk(image, result, i, j + 1, name, row, column);
        }
        // draw top
        if (j - 1 >= 0) {
            drawAsterisk(image, result, i, j - 1, name, row, column);
        }
    }
}
user_30879990
Related