Trova più grande area a matrice 2D in C++

Question

ho bisogno di scrivere funzione ricorsiva in C++ che trova la più grande area del numero '1' a matrice 2D che contiene solo 1 o 0.

Esempio:

int Arr[5][8] = 
{ 
{ 0, 0, 0, 0, 1, 1, 0, 0, }, 
{ 1, 0, 0, 1, 1, 1, 0, 0, }, 
{ 1, 1, 0, 1, 0, 1, 1, 0, }, 
{ 0, 0, 0, 1, 1, 1, 1, 0, }, 
{ 0, 1, 1, 0, 0, 0, 0, 0, }, 
}; 

visivo esempio http://s23.postimg.org/yabwp6h23/find_largest.png

più grande area di questa matrice è di 12, il secondo più grande è 3 e il terzo più grande è 2.

pensavo di fare questo con qualcosa di simile a fl ood algoritmo di riempimento, ma non riesco a capire come.

Answer 1

pensavo di fare questo con qualcosa di simile a Riempi algoritmo

Penso che sia un buon modo per farlo. Applicare riempimento riempimento a qualsiasi 1, contando quelli e sostituendoli con zeri.

Ripetere fino a quando la griglia è composta interamente da zero.

Quanto segue stampa le dimensioni dei componenti collegati in nessun ordine particolare:

#include <iostream> 

constexpr int N = 5; 
constexpr int M = 8; 

int arr[N][M] = 
{ 
{ 0, 0, 0, 0, 1, 1, 0, 0, }, 
{ 1, 0, 0, 1, 1, 1, 0, 0, }, 
{ 1, 1, 0, 1, 0, 1, 1, 0, }, 
{ 0, 0, 0, 1, 1, 1, 1, 0, }, 
{ 0, 1, 1, 0, 0, 0, 0, 0, }, 
}; 

int fill(int arr[N][M], int r, int c) { 
    int count = 0; 
    if (r < N && arr[r][c]) { 
    for (int i = c; i >= 0 && arr[r][i]; --i) { 
     arr[r][i] = 0; 
     count += fill(arr, r + 1, i) + 1; 
    } 
    for (int i = c + 1; i < M && arr[r][i]; ++i) { 
     arr[r][i] = 0; 
     count += fill(arr, r + 1, i) + 1; 
    } 
    } 
    return count; 
} 

int print_components(int arr[N][M]) { 
    for (int r = 0; r < N; ++r) { 
    for (int c = 0; c < M; ++c) { 
     if (arr[r][c]) { 
     std::cout << fill(arr, r, c) << std::endl; 
     } 
    } 
    } 
} 

int main() { 
    print_components(arr); 
} 

Answer 2

qualcosa di simile,

int max_area = 0; 

foreach y 
    foreach x 
     if (pos[y][x] == 1 && !visited[y][x]) 
     { 
      int area = 0; 
      Queue queue = new Queue(); 
      queue.push(new Point(x, y)); 
      visited[y][x] = true; 

      while (!queue.empty()) 
      { 
       Point pt = queue.pop(); 
       area++; 

       foreach neightboor of pt (pt.x±1, pt.y±1) 
        if (pos[neightboor.y][neightboor.x] == 1 && !visited[neightboor.y][neightboor.x]) 
        { 
         visited[neightboor.y][neightboor.x] = true; 
         queue.push(new Point(neightboor.x, neightboor.y)); 
        } 
      } 

      if (area > max_area) 
       max_area = area; 
     } 

Answer 3

approccio rapido, ma non so se v'è un modo per farlo in modo corretto (chiamata ricorsiva per ogni elemento non scala per C++ perché lo stack di chiamate è limitato)

int maxy = 5 
int maxx = 8 

int areasize(int x, int y) { 
    if (x < 0 || y < 0 || x > maxx || y > maxy || !Arr[y][x]) 
     return 0; 

    Arr[y][x] = 0; 

    return 1 
      + areasize(x + 1, y) 
      + areasize(x - 1, y) 
      + areasize(x, y + 1) 
      + areasize(x, y - 1); 
} 

maxarea = 0; 

for (int y = 0; y < maxy; y++) { 
    for (int x = 0; x < maxx; x++) { 
     maxarea = std::max(maxarea, areasize(x, y)); 
    } 
} 

Answer 4

bool visited[5][8]; 
int i,j; 
// variables for the area: 
int current_area = 0, max_area = 0; 
int Arr[5][8]={ // type your map of values here 
} 

// functions 

void prepare_visited_map() { 
    for(i=0;i<5;i++) { 
     for(j=0;j<8;j++) visited[i][j] = false; 
    } 
} 

// recursive function to calculate the area around (x,y) 
void calculate_largest_area(int x, int y) { 
    if(visited[x][y]) return; 
    // check if out of boundaries 
    if(x<0 || y<0 || x>=5 || y>=8) return; 
    // check if the cell is 0 
    if(!Arr[x][y]) { 
     visited[x][y] = true; 
     return; 
    } 

    // found a propper cell, proceed 
    current_area++; 
    visited[x][y] = true; 
    // call recursive function for the adjacent cells (north, east, south, west) 
    calculate_largest_area(x,y-1); 
    calculate_largest_area(x+1,y); 
    calculate_largest_area(x,y+1); 
    calculate_largest_area(x-1,y); 
    // by the end of the recursion current_area will hold the area around the initial cell 
} 

// main procedure where the above functions are used 
int mian() { 
    // calculate the sorrounding area of each cell, and pick up the largest of all results 
    for(i=0;i<5;i++) { 
     for(j=0;j<8;j++) { 
      prepare_visited_map(); 
      calculate_largest_area(i,j); 
      if(current_area > max_area) max_area = current_area; 
     } 
    } 
    printf("Max area is %d",max_area"); 
} 

Spero che questo è stato utile :)