如何計算網格中連接的單元格？

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))