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.

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.