Dev Faq
8
votes

Trouver une plus grande surface dans une matrice 2D en C ++

J'ai besoin d'écrire une fonction récursive en C ++ qui trouve la plus grande surface de numéro '1' dans une matrice 2D contenant seulement 1 ou 0.

Exemple: P> 

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

3 commentaires

Le remplissage des inondations fonctionnerait. Si vous êtes coincé quelque part, vous devriez poster votre tentative et décrire votre problème.

Peut-être que pour chaque élément qui équivaut à 1 vérifiez vers le nord, le sud-est et l'ouest puis une augmentation et vérifiez à nouveau. En outre, ajoutez des indices de réseau incrémentés à une liste ignorée. Il y a tellement d'algorithmes de remplissage d'inondations qu'il serait intéressant de savoir quel est le meilleur.

une question connexe est Stackoverflow.com/questions/2478447/...

4 Réponses :

2
votes

Je pensais faire cela avec quelque chose de similaire à l'algorithme de remplissage d'inondation

Je pense que c'est un très bon moyen de le faire. Appliquez le remplissage des inondations à tout 1 , en comptant ceux et les remplaçant avec des zéros.

répéter jusqu'à ce que la grille soit entièrement composée de zéros.

Ce qui suit sera imprimé sur les tailles des composants connectés sans ordre particulier: xxx

1 commentaires

Je ne sais pas comment vous voulez faire cela, mais vous devez faire attention si vous remplacez le 1 S avec 0 's. Sinon, vous pourriez couper une surface connectée en deux et ne reconnaissez plus qu'ils appartenaient ensemble au début.

1
votes

quelque chose comme, xxx

1 commentaires

BTW: OP demandait une solution récursive, afin que les inondations se remplissent et se retrouvent ensemble devraient fonctionner

1
votes

approche rapide, mais je ne sais pas s'il y a un moyen de le faire de manière saine (récursif L'appel à chaque élément n'éduit pas pour C ++ car la pile d'appel est limitée) 

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

1 commentaires

Merci pour l'indice, j'ai oublié d'insérer la déclaration d'effacement.

3
votes 
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");
}
Hope this was helpful :)
0 commentaires

Articles qui pourrait vous intéresser :

Empilez plusieurs colonnes en une sans ignorer les cellules vides
Recherche du nombre de doublons uniquement et uniquement à la fin d'un tableau numpy
JS: filtre le tableau d'objets par valeur maximale par catégorie
Faire pivoter les éléments d'un tableau