python - Filtering a binary matrix to only contain groups that meet a minimum size

Question

I am given an arbitrary binary matrix of the form:

Input = [
[0,0,0,0,0],
[0,0,1,1,0],
[0,1,1,1,0],
[1,0,0,0,1]
]

My objective is to filter this binary matrix so it only contains "islands" of size n or bigger. I am only searching horizontally and not wrapping around matrix edges. If for example, I wanted islands of size 2 or bigger, the output would be:

Output = [
[0,0,0,0,0],
[0,0,1,1,0],
[0,1,1,1,0],
[0,0,0,0,0]
]

I am having trouble figuring out how to set this problem up. I know I need to do to a nested for loop to search through but I don't know how to generalize this problem so it works for any size island or any arbitrary matrix. The first thought that came to mind was DFS but I am not too sure how to implement DFS with a minimum island condition. Also I am only searching horizontally, not vertically and not wrapping around matrix edges. Any thoughts or tips on this problem would be greatly appreciated.

question from:https://stackoverflow.com/questions/65602438/filtering-a-binary-matrix-to-only-contain-groups-that-meet-a-minimum-size

Answer 1

Here is what does my solution (not sure it is exactly what you're expecting) :

? Keeps any row having at least one island and discards others

? Accepts several islands in a same row

? Sets any column not member of an island to zero

#include <iostream>
#include <string.h>

#define SIZE 6
#define ISLAND 2

void printMatrix(char matrix[SIZE][SIZE], char limit) {
    for (int i=0; i<limit; i++) { 
        for (int j=0; j<SIZE; j++) { 
            printf("%d,", matrix[i][j]);
        }
        printf("
");
    }
}

int main() {
    
    // Fills a matrix with random 1 and 0 and prints it
    srand(time(NULL));
    char matrix[SIZE][SIZE] = {0};
    for (int i=0; i<SIZE*SIZE; i++) { matrix[i/SIZE][i%SIZE] = (char)(rand() % 2); }
    printMatrix(matrix, SIZE);

    // The matching rows will be copied in a second matrix
    char result[SIZE][SIZE] = {0};
    char resultCount = 0;
    
    // Filtering
    for (int i=0; i<SIZE; i++) {
        bool found = false;
        char start = -1;
        for (int j=0; j<SIZE; j++) { 
            if (matrix[i][j]) {
                start = j;
                while (j < SIZE && matrix[i][j]) j++;
                if (j - start >= ISLAND) found = true;
                else for (char k=start; k<j; k++) matrix[i][k] = 0;
            }
        }
        if (found) {
            memcpy(result + resultCount, matrix[i], SIZE);
            resultCount++;
        }
    }
    //Prints the result
    printf("%d row(s) found :
", resultCount);
    printMatrix(result, resultCount);
    return 0;
}