如何计算网格中连接的单元格？

Question

我正试图解决Hackerrank问题"Connected Cells in a Grid"。任务是在网格中找到最大区域（连接的单元格）。

我的方法是添加我发现的数量，只有当元素还没有被访问过时，那么我将取最大值的几条路径。它似乎不适用于以下测试用例：

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

Answer 1

我认为将这个程序制定为connected components问题是很自然的。具体来说，我用boost::graph这个。

这个想法是建立一个图表，其矩阵中的每个条目是一个节点，并且在水平和垂直1个条目之间存在边缘。一旦建立了这样一个图，所需要的就是运行连接组件算法，并找到最大的组件。

下面的代码这样做：

#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 

注意，程序编码I，J（对于其中尺寸为5的情况下）通过5 i + j。这很容易反转。

Answer 2

可以代表矩阵为无向图，并使用DFS或BFS找到connected component最节点：含有1每一个细胞都可以成为节点，并且有一个边缘两者之间节点，如果相应的单元格是相邻的。

Answer 3

如果您仍需要一些指导与解决方案，here is mine in Python - 通过了所有测试:)（访问我github看，我已经用C解决还有其他挑战++以及）

def getBiggestRegion(grid, n, m): 
    max_region = 0 
    region_size = 0 
    for i in xrange(n): 
     for j in xrange(m): 
      if grid[i][j] == 1: 
       region_size = mark_region(grid, i, j, n, m) 
       #region_size += 1 
       if region_size > max_region: 
        max_region = region_size 
    return max_region 


def push_if_valid(stack, i, j, n, m): 
    if 0 <= i < n and 0 <= j < m: 
     stack.append((i, j)) 

dirs = [[1,0], [0,1], [-1,0], [0,-1], [-1,-1], [-1, 1], [1,1], [1, -1]] 
def mark_region(grid, i, j, n, m): 
    stack = [] 
    stack.append((i, j)) 
    region_size = 0 
    while stack: 
     curr = stack.pop() 
     ci = curr[0] 
     cj = curr[1] 
     if grid[ci][cj] == 1: 
      grid[ci][cj] = 2 
      region_size += 1 
      #this for loop is for going in all the directions 
      #North, South, East, West, NW, SW, SE, NE 
      #in my C++ Pacman sol, I have the actual lines instead 
      for dir in dirs: 
       push_if_valid(stack, ci + dir[0], cj + dir[1], n, m) 

    return region_size 

n = int(raw_input().strip()) 
m = int(raw_input().strip()) 
grid = [] 
for grid_i in xrange(n): 
    grid_t = list(map(int, raw_input().strip().split(' '))) 
    grid.append(grid_t) 
print(getBiggestRegion(grid, n, m))