How to find binaries start, end index and their total count in 2D matrix

Question

1.00/5 (3 votes)

See more:

I have a matrix of size m x n as given below. I need the count of cluster of 1s such that it must have at least 1 neighbor with 1. The Neighbor of element (i,j) are (i-1,j),(i+1,j) and (i-1,j-1).

The output of the following matrix should be 6.

I need a dynamic programming algorithm:

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	0	1	1	0	0	1	1	0	0	0	0	0	0	0
0	1	1	1	0	0	1	0	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0	0	0	0	0	0
0	1	1 0	0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	0	0	0	1	1	0	0	0
0	0	0	0	0	0	0	0	0	1	1	1	0	0	0
0	0	1	1	0	0	0	0	0	1	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	1	1	0	0	0	0
0	0	0	0	0	0	0	0	1	1	0	0	0	0	0
0	0	0	0	0	0	0	0	1	1	0	0	0	0	0
0	0	0	0	0	0	0	1	1	1	1	0	0	1	0
0	0	0	0	0	0	0	0	0	0	0	1	1	0	0
0	0	0	0	0	0	0	0	0	0	1	1	1	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

What I have tried:

I am not getting the correct answer.

Posted 22-Aug-23 18:47pm

Muhammad Usama Aug2023

Updated 29-Aug-23 1:51am

Deeksha Shenoy

v2

Add a Solution

Comments

merano99 24-Aug-23 3:42am

Without the code, no one here can guess why the expected result is not coming out. The code posted as a Solution does not seem to take into account several things.
Please move your own Solution to the question and comment on what exactly is wrong.
The definition of neighbors is not symmetric and would declare a single diagonal connection as a neighbor, but only in one direction.
This seems neither reasonable nor correct. If you define the neighbors above, below, right and left as usual and also apply the DFS as in my Solution 3, the result for the example is exactly 6.

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

merano99 · Answer 1 · 2023-08-23T14:02:00

Depth-First Search (DFS) would be the appropriate algorithm to find connected components in a graph (in this case, in a matrix). In your case, it can be used to identify contiguous clusters of ones in a binary matrix.

To begin with, an empty list cluster is needed to store the coordinates of the points in the current cluster. An additional matrix visited is also used to store which points have already been visited. At the beginning all points are to be marked as "not visited".

The DFS search is now started at any first point that has the value 1 in the matrix.

The search usually includes neighboring points of the current point. This is typically done in four directions (up, down, left, right). For each neighbor point that has the value 1 and has not yet been visited, the DFS search is called recursively.

When the DFS search is complete, you have found all contiguous points in the cluster, and the cluster list contains their coordinates.

The DFS search continues until all points in the matrix have been visited. Each time a cluster is found, it is added to the clusters list if it consists of at least 2 points.

C++

typedef std::vector<std::vector<int>> MatrixType;
typedef std::vector<std::vector<int>> ClusterType;
typedef std::vector<ClusterType> ClusterListType;

// Data in 2D matrix
MatrixType const data = {  ... };

bool isValid(int x, int y, int rows, int cols) {
    return x >= 0 && x < cols&& y >= 0 && y < rows;
}

bool isNeighbor(const MatrixType& matrix, int pos_y, int pos_x);

// recursive dfs function, searches all connected points
void dfs(const MatrixType& matrix, int pos_y, int pos_x, std::vector<std::vector<bool>>& visited, ClusterType& cluster);

int findClusters(const MatrixType& matrix, ClusterListType& clusters) 
{
    int rows = matrix.size();
    int cols = matrix[0].size();
    clusters.clear();
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));

    for (int y = 0; y < rows; ++y) {
        for (int x = 0; x < cols; ++x) {
            if (matrix[y][x] == 1 && !visited[y][x]) {
                ClusterType cluster;
                dfs(matrix, y, x, visited, cluster);
                if (cluster.size() >= 2) { // Add clusters with at least 2 points
                    clusters.push_back(cluster);
                }
            }
        }
    }
return clusters.size();
}

int main() 
{
    ClusterListType clusters;
    int numClusters = findClusters(data, clusters);
    std::cout << "Number of clusters: " << numClusters << "\n";
}

If you don't need the list of clusters with the respective connected points, a simple counter is sufficient and you can omit the parameter ClusterListType.
The call is then simplified to: int findClusters(const MatrixType& matrix);

Note: The code is deliberately not a complete solution, but is an aid to the solution path. The code is tested and the expected result will come out once it is completed. A finished final solution would be mostly undesirable here without the questioner's own contribution.

OriginalGriff · Answer 2 · 2023-08-22T19:04:00

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]

Muhammad Usama Aug2023 · Answer 3 · 2023-08-22T21:41:00

import numpy as np
from scipy.ndimage import label

def dynamic_find_events(matrix, connection_structure):
    num_rows, num_cols = matrix.shape
    num_events = 0
    events = []

    # Dynamic programming table to track events at each cell
    event_table = np.zeros_like(matrix, dtype=int)

    for i in range(num_rows):
        for j in range(num_cols):
            if matrix[i, j] == 1:
                neighbors = []
                for dx, dy in connection_structure:
                    ni, nj = i - dx, j - dy
                    if 0 <= ni < num_rows and 0 <= nj < num_cols and matrix[ni, nj] == 1:
                        neighbors.append(event_table[ni, nj])

                if not neighbors:
                    num_events += 1
                    event_table[i, j] = num_events
                    events.append([(i, j), (i, j)])  # Start and end indices
                else:
                    min_event = min(neighbors)
                    event_table[i, j] = min_event
                    events[min_event - 1][1] = (i, j)

    return num_events, events



# Your 2D matrix
data = np.array([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
])


connection_structure = [(0, 1), (1, 0), (1, 1)]

num_events, events = dynamic_find_events(data, connection_structure)

print(f"Number of events: {num_events}")
for i, event in enumerate(events):
    print(f"Event {i + 1}: Start Index {event[0]}, End Index {event[1]}")

How to find binaries start, end index and their total count in 2D matrix

3 solutions

Solution 3

Solution 1

Solution 2

Add your solution here

Preview 0