グリッド内の接続されたセルをカウントするには？

Question

私はHackerrank問題"Connected Cells in a Grid"を解決しようとしています。タスクは、グリッド内で最大の領域（1からなる接続セル）を見つけることです。

私のアプローチは、要素がまだ訪問されていない場合にだけ見つかるものの数を追加し、次にいくつかのパスの最大値を取ることでした。次のテストケースでは機能していないようです：

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と垂直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; 
} 

出力は、プログラムが5によって（寸法が5である場合）I、Jをコードすること

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。これは簡単に可逆的です。

Answer 2

あなたは無向グラフとして行列を表し、ほとんどのノードとconnected componentを見つけるためDFS又はBFSを使用することができます。1を含むすべてのセルは、ノードになることができ、両者のエッジがあります対応するセルが隣接している場合にはノードとなる。

Answer 3

あなたはまだ解決策、here is mine in Pythonといくつかのガイダンスが必要な場合は、 - すべての試験:)（私もC++でそこに解決した他の課題を確認するために私のgithubを訪問）

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

に合格しました