Click here to Skip to main content
15,907,395 members
Please Sign up or sign in to vote.
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
Updated 29-Aug-23 1:51am
v2
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.

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.
 
Share this answer
 
v3
Comments
Andre Oosthuizen 24-Aug-23 5:13am    
My +5
merano99 24-Aug-23 5:46am    
Thx!
CPallini 25-Aug-23 7:25am    
5.
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[^]
 
Share this answer
 
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]}")
 
Share this answer
 
Comments
Patrice T 23-Aug-23 6:00am    
Use Improve question to update your quest
And then, remoce this non solution.ion.
So that everyone can pay attention to this information.

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900