如何计算网格中的已连接电池? [英] How to count connected cells in a grid?

问题描述

我正在尝试解决Hackerrank问题网格" .任务是在网格中找到最大的区域(由一个单元组成的连通单元).

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

我的方法出问题了吗?

#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;
}

推荐答案

我认为将此程序表述为已连接的组件问题.具体来说，我使用了 boost::graph 为此.

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

这个想法是建立一个图，矩阵的每个入口都是一个节点，并且水平和垂直1入口之间都有边.一旦建立了这样的图形，所有要做的就是运行连接的组件算法，并找到最大的组件.

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.

以下代码这样做:

#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;
}

输出为

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

请注意，程序使用 5 i + j 对 i，j (对于尺寸为5的情况)进行编码.这很容易反转.

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

这篇关于如何计算网格中的已连接电池?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！