template boy - 1 year ago 54

C++ Question

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 Source

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.