I need to find an alternate for recursion to solve this problem

Question

Note: I would prefer an algorithm or code in c language, thank you in advance.

Suppose I have a 5x5 2D array.

00, 00, 01, 01, 00 
01, 00, 01, 01, 00 
01, 00, 00, 01, 01 
01, 01, 00, 00, 00 
01, 00, 00, 01, 01

Criteria for grouping :- All the 1s (01s) in the array that are connected to each other from up, down, left, right or diagonally belongs to the same group.

Now, I want to group all the 1s (01s) together without recursion in such a way that my array looks like:-

00, 00, 02, 02, 00 
01, 00, 02, 02, 00 
01, 00, 00, 02, 02 
01, 01, 00, 00, 00 
01, 00, 00, 03, 03

At last I output how many groups there are. Here, I output 3.

Say I find the connection from one index position, suppose I am at i=1 and j=0. Now using nested loops I can find all connections from the position I am at.

for(int i=-1; i<2; i++){
    for(int j=-1; j<2; j++){
}}

But how do I find the connections from a connection? Say I find all connections from i=1, j=0. If I found a 1 at i=1,j=1 then how do I continue my search again? Here recursion seems easy but how should I do this without recursion?

Here is what I have so far. I have no time bound limit so I am doing this stupidly.

void printImgArray(int array[L][L])
{
  
    printf("------ Image Contents -------\n");
    int i, j;
    for (i=0; i<L; i++)
    {
    for (j=0; j<L; j++)
        printf("%02d, ",array[i][j]);
    printf("\n");
    }
    printf("-----------------------------\n");
}

int checkIndex(int i, int j){
    return i >= 0 && j>=0 && i< L && j< L;
}

int colorNonRecursively(int image[L][L]) {
  int copyArray[L][L] = {0};
  int i, j, new_i, new_j;
  int counter = 1;

  for(i=0; i<L; i++){
    for(j=0; j<L; j++){
      for(new_i=-1; new_i<2; new_i++){
        for(new_j=-1; new_j<2; new_j++){
          if(copyArray[i][j] != 1 && image[i][j] != 0){
            copyArray[i][j] = 1;
            image[i][j] = counter;

            if(checkIndex(i+new_i, j+new_j)){
              if(copyArray[i+new_i][j+new_j] != 1 &&
                image[i+new_i][j+new_j] != 0){
                copyArray[i+new_i][j+new_j] = 1;
                image[i+new_i][j+new_j] = counter;
              }
            }
          }
        }
      }
      counter++;
    }
  }

int main(){

    int cellImg[L][L]={{0,0,1,1,0},\
                     {1,0,1,1,0},\
                     {1,0,0,1,1},\
                     {1,1,0,0,0},\
                     {1,0,0,1,1}};
    printImgArray(cellImg);
    colorNonRecursively(cellImg);
    printImgArray(cellImg);
    return 0;
}

Input 2D array:-

00, 00, 01, 01, 00 
01, 00, 01, 01, 00 
01, 00, 00, 01, 01 
01, 01, 00, 00, 00 
01, 00, 00, 01, 01

Output 2D array:-

00, 00, 03, 04, 00 
06, 00, 08, 09, 00 
11, 00, 00, 14, 15 
16, 17, 00, 00, 00 
21, 00, 00, 24, 25 

Here I can see that my counter is placed at the right location but grouping is not done correctly. I know this code has a running time of N^4 but in my case it does not matter so please ignore it. How can I group these correctly so that I have this array as output?

Output 2D array(that should be):-

00, 00, 02, 02, 00, 
01, 00, 02, 02, 00, 
01, 00, 00, 02, 02, 
01, 01, 00, 00, 00, 
01, 00, 00, 03, 03, 

Answer 1

You could create a graph representation of that array, such that 1's are the nodes and the edges are the neighboring 1's. After that you can do DFS searches through those nodes and label them as the DFS search that was done. So, if it was the first DFS search then the label is 1, if it is the second DFS/BFS search then it is 2, etc. Note that the amount of DFS/BFS searches are the amount of connected components. This way you have a graph with your desired labels. After that, you can convert the graph into an array if you wish. This is also extensible to n dimensions. You can do the graph searches using iterative methods.

Answer 2

Use stupid iteration and data structure:

Build a List of sets of coordinates (index in array): List<Set<Pair<Integer,Integer>>> or List<Set<Integer[]>>

In the first round add a Set for every array element with a 1 to the list.

In the next iterations loop through the sets and check wether 2 can be joined(more looping). remove the 2 sets and add the joined set. next iteration.

If the list don't change anymore your ready with the list of groups.

Implementing would be fun, but I think you want to try yourself...

I was right, it was fun(Sorrry for Java, but no streams):

public class Groups
{

    public static void main(String[] args)
    {
        Integer[][] table = {
                    {00, 00, 01, 01, 00},
                    {01, 00, 01, 01, 00},
                    {01, 00, 00, 01, 01},
                    {01, 01, 00, 00, 00},
                    {01, 00, 00, 01, 01},
                };

        List<Set<Integer[]>> groups = createInitial(table);

        groups = findgroups(groups);
        print(table,groups);
    }

    private static void print(Integer[][] table, List<Set<Integer[]>> groups)
    {
        int groupid = 0;
        for (Set<Integer[]> group : groups) {
            groupid++;
            for (Integer[] element : group) {
                table[element[0]][element[1]] = groupid;
            }
        }
        for (int i = 0; i < table.length; i ++) {
            for (int j = 0; j < table[i].length; j ++) {
                System.out.print(table[i][j]+ " ");
            }
            System.out.println();
        }

    }

    private static List<Set<Integer[]>> findgroups(List<Set<Integer[]>> groups)
    {
        int before;
        int after;
        do {
            before = groups.size();
            join(groups);
            after = groups.size();

        } while (before != after);
        return groups;
    }

    private static void join(List<Set<Integer[]>> groups)
    {
        for (int i = 0; i < groups.size(); i++) {
            for (int j = i+1; j < groups.size(); j++) {
                if (joins(groups.get(i),groups.get(j))) {
                    groups.get(i).addAll(groups.get(j)); // the joined group
                    groups.remove(j);                    // delete the other 
                    return;
                }
            }
        }
    }

    private static boolean joins(Set<Integer[]> group1, Set<Integer[]> group2)
    {
        for (Integer[] element1 : group1) {
            for (Integer[] element2 : group2) {
                if (adjacent(element1,element2)) {
                    return true;
                }
            }
        }
        return false;

    }

    private static boolean adjacent(Integer[] element1, Integer[] element2)
    {
        return ((Math.abs(element1[0] - element2[0]) < 2) && (Math.abs(element1[1] - element2[1]) < 2));
    }

    private static List<Set<Integer[]>> createInitial(Integer[][] table)
    {
        List<Set<Integer[]>> init = new ArrayList<>();
        for (int i = 0; i < table.length; i ++) {
            for (int j = 0; j < table[i].length; j ++) {
                if (table[i] [j] > 0) {
                    Set<Integer[]> single = new HashSet<>();
                    Integer[] element = {i,j};
                    single.add(element);
                    init.add(single);
                }
            }
        }
        return init;
    }

}

Output:

0 0 1 1 0 
2 0 1 1 0 
2 0 0 1 1 
2 2 0 0 0 
2 0 0 3 3 

Answer 3

Loop through your 2d array, every time you encounter a 1 and the index as not been visited, run bfs.

During bfs, remember which indexes you have already visited (either through bfs or main loop). This can be done through a boolean array.

The following is some code in c++. A C implementation of a queue can be found here

#include<stdio.h>
#include<queue>

int arr[5][5] = {
    {00, 00, 01, 01, 00},
    {01, 00, 01, 01, 00},
    {01, 00, 00, 01, 01},
    {01, 01, 00, 00, 00},
    {01, 00, 00, 01, 01},
};

int output[5][5];

// two arrays that help with directions
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0},
    dy[8] = {1, 0, -1, 1, 1, 0, -1, -1};

int vis[5][5];

int count = 1;

std::queue<int> qx, qy;

void bfs(int x, int y){
    // start bfs my pushing starting position into respective queues
    // and marking starting position as visited
    qx.push(x); qy.push(y);
    vis[x][y] = 1;
    output[x][y] = count;

    // loop until queue is empty
    while (!qx.empty()){
        int cur_x = qx.front(), cur_y = qy.front();
        qx.pop(); qy.pop();

        // loop 0..8, for 8 directions
        for (int i=0; i<8; i++){

            // make sure next node fits constraints
            if (cur_x + dx[i] >= 0 && cur_x + dx[i] < 5){
                if (cur_y + dy[i] >= 0 && cur_y + dy[i] < 5){

                    // check if next node has not been visited
                    // and its position in arr is 1
                    if (vis[ cur_x + dx[i] ][ cur_y + dy[i] ] == 0 &&
                        arr[ cur_x + dx[i] ][ cur_y + dy[i] ] == 1){

                        // mark next node as visited
                        // and push into queue
                        vis[ cur_x + dx[i] ][ cur_y + dy[i] ] = 1;
                        qx.push(cur_x + dx[i]);
                        qy.push(cur_y + dy[i]);
                        output[ cur_x + dx[i] ][ cur_y + dy[i] ] = count;
                    }
                }
            }
        }
    }
}
int main(){
    for (int i=0; i<5; i++){
        for (int j=0; j<5; j++){
            if (arr[i][j] == 1 && vis[i][j] == 0){
                // bfs will fill one "section"
                bfs(i, j);
                count++;
            }
        }
    }

    // print output
    for (int i=0; i<5; i++){
        for (int j=0; j<5; j++){
            printf("%d ", output[i][j]);
        }
        printf("\n");
    }
    // printf("%d\n", count);
}