Finden größte Fläche in 2D-Array in C++

Question

I rekursive Funktion in C++ geschrieben werden muss, die größte Fläche der Nummer findet '1' in der 2D-Array, die

Beispiel nur 1 oder 0 enthält:

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

Visuelles Beispiel: http://s23.postimg.org/yabwp6h23/find_largest.png

größte Fläche dieser Anordnung 12 ist, die zweitgrößte ist 3 und drittgrößte 2.

ich dachte, dies mit zu fl ähnlich, etwas zu tun ood füllen Algorithmus, aber kann einfach nicht herausfinden, wie.

Answer 1

Ich dachte, dies ähnlich mit etwas zu tun Algorithmus fuell

Ich denke, das ist ein ziemlich guter Weg, es zu tun. Wenden Sie flood fill auf 1 an, zählen Sie die Einsen und ersetzen Sie sie durch Nullen.

Wiederholen, bis das Raster vollständig aus Nullen besteht.

Im Folgenden werden die Größen der angeschlossenen Komponenten in keiner bestimmten Reihenfolge ausdrucken:

#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

etwas wie

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

Schnell Ansatz, aber ich weiß nicht, ob es eine ist Möglichkeit, dies auf vernünftige Weise zu tun (rekursiver Aufruf für jedes Element skaliert nicht für C++, da der Aufrufstapel begrenzt ist)

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

Hoffnung, das war hilfreich :)