How to know if there are numbers followed vertically and horizontally in a recursive c ++ matrix?

Navigation
0

I have the following matrix: 

1 0 0 1 0 0
0 1 0 0 0 0
0 1 1 0 0 0
0 0 0 1 1 1
0 1 1 0 1 1

The 1 's represent the "islands" (numbers followed vertically and horizontally), which refers to being together. How can I know which numbers are together and how many islands there are, recursively?

In this case there are 5 islands because of the following: 

1 - - - - -      - - - 1 - -      - - - - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - 1 - - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - 1 1 - - -      - - - - - -      - - - - - -
- - - - - -      - - - - - -      - - - - - -      - - - 1 1 1      - - - - - -
- - - - - -      - - - - - -      - - - - - -      - - - - 1 1      - 1 1 - - -

I have the following code, but without recursion (does what is needed but is not recursive) or can the code be recursive?: 

double conjuntoIslas(int a[][6]){
 int contCol, contFil, pivofil, pivocol, auxFil, auxCol;
 double sum = 0, island = 0;
 bool bol = false;
 contCol = 5;
 contFil = 4;
 while(contCol >= 0 && contFil >= 0){   
  if(a[contFil][contCol] == 1){
   pivofil = contFil;
        pivocol = contCol;
        auxFil = contFil;
        auxCol = contCol;

        cout<<endl<<endl<<"CUADRO EN: "<<contFil<<", "<<contCol<<endl;

        while(pivofil > 0){
            if(a[pivofil-1][pivocol] == 1){
                cout<<endl<<"\t"<<"Cuadro ARRIBA de: "<<pivofil<<", "<<pivocol;
                sum += 1;
                a[pivofil][pivocol] = 0;
                a[pivofil-1][pivocol] = 0;
                pivocol = auxCol;
                while(pivocol > 0){
                    if(a[pivofil-1][pivocol-1] == 1){
                        sum += 1;
                        cout<<endl<<"\t"<<"Cuadro IZQUIERDA de: "<<pivofil-1<<", "<<pivocol;
                        a[pivofil-1][pivocol-1] = 0;
                        pivocol--;
                    }
                    else{
                        pivocol = 0;
                    }
                }
                a[pivofil-1][pivocol] = 0;

                pivocol = auxCol;

                pivofil--;
            }
            else{
                pivofil = 0;
            }
        }
        pivofil = auxFil;
        while(pivocol > 0){
            if(a[pivofil][pivocol-1] == 1){
                cout<<endl<<"\t"<<"Cuadro a la IZQUIERDA de: "<<pivofil<<", "<<pivocol;
                sum += 1;
                a[pivofil][pivocol] = 0;
                a[pivofil][pivocol-1] = 0;
                pivofil = auxFil;
                while(pivofil > 0){
                    if(a[pivofil-1][pivocol-1] == 1){
                        cout<<endl<<"\t"<<"Cuadro ARRIBA de: "<<pivofil<<", "<<pivocol-1;
                        sum += 1;
                        a[pivofil-1][pivocol-1] = 0;
                        pivofil--;
                    }
                    else{
                        pivofil = 0;
                    }
                }
                pivofil = auxFil;
                a[pivofil][pivocol-1] = 0;
                pivocol--;
            }
            else{
                pivocol = 0;
            }
        }
        island += sum/sum;
        a[contFil][contCol] = 0;

    }
    if(contCol == 0){
        contFil--;
        contCol = 5;
    }
    else{
        contCol--;
    }
}
return island;
}
    
asked by Bruno 03.07.2018 в 06:42
source

1 answer

3

It seems an appropriate case to use the Filled by Diffusion (Floodfill in English). The pseudocode of that algorithm could be:

  • If the cell is not visited.
  • Marks the cell as visited.
  • If the cell is busy.
    • Save the coordinate.
    • Visit the upper, lower, left and right cells.

    • As you can see, the algorithm is recursive if point 2 is fulfilled. The way I have implemented it is by first creating a coordinate object and aliases to facilitate the task: 

    struct coordenada { int x{}, y{}; };
using coordenadas = std::vector<coordenada>;
using islas = std::vector<coordenadas>;

    Then we create a function (template) that receives a generic bidimensional 1 training on which to look for islands: 

    template <int H, int W>
islas busca_islas(int (&matriz)[H][W])
{
    bool visitado[W][H]{};
    islas resultado{};

    for (int h = 0; h < W; ++h)
    {
        for (int v = 0; v < H; ++v)
        {
            coordenadas isla{};
            busca_islas({v, h}, isla, matriz, visitado);
            if (!isla.empty())
            {
                resultado.push_back(isla);
            }
        }
    }

    return resultado;
}

    The coordinates v (vertical) and h (horizontal) are reversed (the y before the x ) because int[6][6] means six rows of six columns no six columns of six rows . This function that only receives a formation of HxW (Height x Width) elements calls an overload that is what makes the recursion: 

    template <int H, int W>
void busca_islas(const coordenada &c, coordenadas &resultado, int (&matriz)[H][W], bool (&visitado)[H][W])
{
    if (!visitado[c.y][c.x])
    {
        visitado[c.y][c.x] = true;

        if (matriz[c.y][c.x] == 1)
        {
            resultado.push_back(c);
            busca_islas({std::max(c.x - 1, 0), c.y}, resultado, matriz, visitado);
            busca_islas({std::min(c.x + 1, W - 1), c.y}, resultado, matriz, visitado);
            busca_islas({c.x, std::max(c.y - 1, 0)}, resultado, matriz, visitado);
            busca_islas({c.x, std::min(c.y + 1, H - 1)}, resultado, matriz, visitado);
        }
    }
}

    The calls to std::min and std::max are not to leave the ranges of the training 1 .

    Applying that code on your data I get the following islands: 

    { {0, 0} }
{ {3, 0} }
{ {1, 1} {1, 2} {2, 2} }
{ {3, 3} {4, 3} {5, 3} {5, 4} {4, 4} }
{ {1, 4} {2, 4} }

    What are you looking for? You can see the code working Here .

  • Also known as an array (or in English: array).
    • answered by 03.07.2018 в 12:48
    Popup window message in PHP Query by date range with many nested queries