15,907,395 members
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
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.

## Solution 3

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.

v3
Andre Oosthuizen 24-Aug-23 5:13am
My +5
merano99 24-Aug-23 5:46am
Thx!
CPallini 25-Aug-23 7:25am
5.

## Solution 1

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[^]

## Solution 2

```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

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]}")```

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.