template boy template boy - 2 months ago 12
C++ Question

How to count connected cells in a grid?

I'm trying to solve the Hackerrank problem "Connected Cells in a Grid". The task is to find the largest region (connected cells consisting of ones) in the grid.

My approach was to add the number of ones I find only if the element hasn't been visited yet, then I take the maximum of several paths. It doesn't seem to be working for the following test case:

5
5
1 1 0 0 0
0 1 1 0 0
0 0 1 0 1
1 0 0 0 1
0 1 0 1 1


Is there something wrong with my approach?

#include <vector>
#include <algorithm>
using namespace std;

#define MAX 10
bool visited[MAX][MAX];

int maxRegion(vector<vector<int>> const& mat, int i, int j) {
int result;

if ((i == 0 && j == 0) || visited[i][j]) {
result = 0;
}
else if (i == 0) {
result = mat[i][j-1] + maxRegion(mat, i, j-1);
}
else if (j == 0) {
result = mat[i-1][j] + maxRegion(mat, i-1, j);
}
else {
result = mat[i-1][j-1] +
max({maxRegion(mat, i-1, j),
maxRegion(mat, i, j-1),
maxRegion(mat, i-1, j-1)});
}
visited[i][j] = true;
return result;
}

Answer

I think it's very natural to formulate this program as a connected components problem. Specifically, I've used boost::graph for this.

The idea is to build a graph whose each entry in the matrix is a node, and there are edges between horizontal and vertical 1 entries. Once such a graph is built, all that is needed is to run the connected components algorithm, and find the biggest component.

The following code does so:

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

using namespace std;
using namespace boost;

int main()
{   
    vector<vector<int>> v{{1, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 0, 1}, {0, 1, 0, 1, 1}};

    typedef adjacency_list <vecS, vecS, undirectedS> graph;

    graph g(v.size() * v.size());

    // Populate the graph edges
    for(size_t i = 0; i < v.size() - 1; ++i)
        for(size_t j = 0; j < v[i].size() - 1; ++j)
        {
            if(v[i][j] == 1 && v[i + 1][j] == 1)
                add_edge(i * v.size() + j, (i + 1) * v.size() + j, g);
            else if(v[i][j] == 1 && v[i][j + 1] == 1)
                add_edge(i * v.size() + j, i * v.size() + j + 1, g);
        }

     // Run the connected-components algorithm.
     vector<int> component(num_vertices(g));
     int num = connected_components(g, &component[0]);

     // Print out the results.
     std::vector<int>::size_type i;
     for(i = 0; i != component.size(); ++i)
         cout << "Vertex (" << i / v.size() << ", " << i % v.size()  << ") is in component " << component[i] << endl;
     cout << endl;
}

The output is

Vertex (0, 0) is in component 0
Vertex (0, 1) is in component 0
Vertex (0, 2) is in component 1
Vertex (0, 3) is in component 2
Vertex (0, 4) is in component 3
Vertex (1, 0) is in component 4
Vertex (1, 1) is in component 0
Vertex (1, 2) is in component 0
Vertex (1, 3) is in component 5
Vertex (1, 4) is in component 6
Vertex (2, 0) is in component 7
Vertex (2, 1) is in component 8
Vertex (2, 2) is in component 0
Vertex (2, 3) is in component 9
Vertex (2, 4) is in component 10
Vertex (3, 0) is in component 11
Vertex (3, 1) is in component 12
Vertex (3, 2) is in component 13
Vertex (3, 3) is in component 14
Vertex (3, 4) is in component 15
Vertex (4, 0) is in component 16
Vertex (4, 1) is in component 17
Vertex (4, 2) is in component 18
Vertex (4, 3) is in component 19
Vertex (4, 4) is in component 20

Note that the program encodes i, j (for the case where the dimension is 5) by 5 i + j. This is easily invertible.

Comments