Atraviese la array en forma diagonal de abajo hacia arriba usando recursividad

Dada una array mat[][] de tamaño N x N , la tarea es atravesar la array en diagonal de forma ascendente utilizando la recursividad .
Recorrido de abajo hacia arriba en diagonal: 

  • Atraviesa la diagonal mayor de la array.
  • Atraviesa la diagonal inferior hasta la diagonal mayor de la array.
  • Atraviesa la diagonal superior hasta la diagonal mayor de la array.
  • Del mismo modo, Atraviesa la array para cada diagonal.

La siguiente imagen muestra el recorrido de abajo hacia arriba de la array. 
 

Ejemplos: 
 

Input: 
M[][] = {{11, 42, 25, 51}, 
         {14, 17, 61, 23},
         {22, 38, 19, 12},
         {27, 81, 29, 71}} 
Output: 
11 17 19 71 
14 38 29 
42 61 12 
22 81 
25 23 
27 
51 

Input: 
M[][] = {{3, 2, 5}, 
         {4, 7, 6},
         {2, 8, 9}}
Output: 
3 7 9 
4 8 
2 6 
2 
5  

Enfoque: la idea es atravesar los elementos de la diagonal mayor de la array y luego llamar recursivamente a la diagonal inferior de la array y la diagonal superior a la diagonal mayor de la array. La definición recursiva del enfoque se describe a continuación:

  • Definición de función: para este problema, habrá los siguientes argumentos de la siguiente manera: 
    • mat[][] // Array a recorrer
    • Fila actual (digamos i ) // Fila actual a recorrer
    • Columna actual (digamos j ) // Columna actual a recorrer
    • Número de filas (por ejemplo , fila )
    • Número de columnas (por ejemplo col )
  • Caso base: el caso base para este problema puede ser cuando la fila actual o la columna actual están fuera de los límites. En este caso, atraviese la otra diagonal inferior, o si la última vez se eligió la diagonal inferior, atraviese la diagonal mayor justo encima de ella.
if (i >= row or j >= col)
    if (flag)
        // Change the Current index
        // to the bottom diagonal
    else
        // Change the current index
        // to the up diagonal of matrix
  • Caso recursivo: Habrá dos casos del recorrido recursivo de la array que se define de la siguiente manera: 
    • Recorrido de la diagonal actual: para recorrer la diagonal actual, incremente la fila y la columna actuales en 1 al mismo tiempo y llame recursivamente a la función.
    • Recorrido de la diagonal inferior/superior: para recorrer la diagonal inferior/superior, llame a la función recursiva con las variables estáticas que almacenan el siguiente punto de inicio transversal de la array.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation to traverse the
// matrix in the bottom-up fashion
// using Recursion
  
#include <iostream>
  
using namespace std;
  
// Recursive function to traverse the
// matrix Diagonally Bottom-up
bool traverseMatrixDiagonally(int m[][5], 
          int i, int j, int row, int col)
{
      
    // Static variable for changing
    // Row and column
    static int k1 = 0, k2 = 0;
      
    // Flag variable for handling
    // Bottom up diagonal traversing
    static bool flag = true;
      
    // Base Condition
    if (i >= row || j >= col) {
          
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag) {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else {
  
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
        cout << endl;
        return false;
    }
      
    // Print matrix cell value
    cout << m[i][j] << " ";
      
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(
           m, i + 1, j + 1, row, col)) {
        return true;
    }
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(
            m, k1, k2, row, col)) {
        return true;
    }
      
    return true;
}
  
// Driver Code
int main()
{
    // Initialize the 5 x 5 matrix
    int mtrx[5][5] = {
        { 10, 11, 12, 13, 14 },
        { 15, 16, 17, 18, 19 },
        { 20, 21, 22, 23, 24 },
        { 25, 26, 27, 28, 29 },
        { 30, 31, 32, 33, 34 }
    };
  
    // Function call 
    // for traversing matrix
    traverseMatrixDiagonally(
            mtrx, 0, 0, 5, 5);
}

Java

// Java implementation to traverse 
// the matrix in the bottom-up 
// fashion using recursion
class GFG{
      
// Static variable for changing
// row and column
static int k1 = 0, k2 = 0;
  
// Flag variable for handling
// bottom up diagonal traversing
static boolean flag = true; 
  
// Recursive function to traverse the
// matrix diagonally bottom-up
static boolean traverseMatrixDiagonally(int m[][], int i,
                                        int j, int row,
                                        int col)
{
      
    // Base Condition
    if (i >= row || j >= col)
    {
          
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
          
        System.out.println();
        return false;
    }
      
    // Print matrix cell value
    System.out.print(m[i][j] + " ");
      
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
      
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
      
    return true;
}
  
// Driver Code
public static void main(String[] args)
{
    // Initialize the 5 x 5 matrix
    int mtrx[][] = { { 10, 11, 12, 13, 14 },
                     { 15, 16, 17, 18, 19 },
                     { 20, 21, 22, 23, 24 },
                     { 25, 26, 27, 28, 29 },
                     { 30, 31, 32, 33, 34 } };
  
    // Function call 
    // for traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
}
}
  
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to traverse the 
# matrix in the bottom-up fashion 
# using Recursion
  
# Static variable for changing 
# Row and column
k1 = 0
k2 = 0
  
# Flag variable for handling 
# Bottom up diagonal traversing
flag = True
  
# Recursive function to traverse the 
# matrix Diagonally Bottom-up
def traverseMatrixDiagonally(m, i, 
                             j, row, col):
    global k1
    global k2
    global flag
  
    # Base Condition
    if(i >= row or j >= col):
  
        # Condition when to traverse 
        # Bottom Diagonal of the matrix
        if(flag):
            a = k1 
            k1 = k2
            k2 = a
            if(flag):
                flag = False
            else:
                flag = True
            k1 += 1
        else:
            a = k1
            k1 = k2
            k2 = a
            if(flag):
                flag = False
            else:
                flag = True
        print()
        return False
        
    # Print matrix cell value
    print(m[i][j], end = " ")
  
    # Recursive function to traverse 
    # The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1, 
                                 j + 1, 
                                 row, col)):
        return True
  
    # Recursive function  
    # to change diagonal
    if(traverseMatrixDiagonally(m, k1, 
                                k2, row, col)):
        return True
    return True
  
# Driver Code
  
# Initialize the 5 x 5 matrix
mtrx=[[10, 11, 12, 13, 14],
      [15, 16, 17, 18, 19],
      [20, 21, 22, 23, 24],
      [25, 26, 27, 28, 29],
      [30, 31, 32, 33, 34]]
  
# Function call  
# for traversing matrix
traverseMatrixDiagonally(mtrx, 0, 
                         0, 5, 5)
  
#This code is contributed by avanitrachhadiya2155

C#

// C# implementation to traverse 
// the matrix in the bottom-up 
// fashion using recursion
using System;
  
class GFG{
      
// Static variable for changing
// row and column
static int k1 = 0, k2 = 0;
  
// Flag variable for handling
// bottom up diagonal traversing
static bool flag = true; 
  
// Recursive function to traverse the
// matrix diagonally bottom-up
static bool traverseMatrixDiagonally(int [,]m, int i,
                                     int j, int row,
                                     int col)
{
      
    // Base Condition
    if (i >= row || j >= col)
    {
          
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            int a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
          
        Console.WriteLine();
        return false;
    }
      
    // Print matrix cell value
    Console.Write(m[i, j] + " ");
      
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
      
    // Recursive function 
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
    return true;
}
  
// Driver Code
public static void Main(String[] args)
{
      
    // Initialize the 5 x 5 matrix
    int [,]mtrx = { { 10, 11, 12, 13, 14 },
                    { 15, 16, 17, 18, 19 },
                    { 20, 21, 22, 23, 24 },
                    { 25, 26, 27, 28, 29 },
                    { 30, 31, 32, 33, 34 } };
  
    // Function call for  
    // traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
}
}
  
// This code is contributed by Amit Katiyar

Javascript

<script>
// Java script implementation to traverse
// the matrix in the bottom-up
// fashion using recursion
  
      
// Static variable for changing
// row and column
let k1 = 0, k2 = 0;
  
// Flag variable for handling
// bottom up diagonal traversing
let flag = true;
  
// Recursive function to traverse the
// matrix diagonally bottom-up
function traverseMatrixDiagonally(m,i,j,row,col)
{
      
    // Base Condition
    if (i >= row || j >= col)
    {
          
        // Condition when to traverse
        // Bottom Diagonal of the matrix
        if (flag)
        {
            let a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
            k1++;
        }
        else
        {
            let a = k1;
            k1 = k2;
            k2 = a;
            flag = !flag;
        }
          
        document.write("<br>");
        return false;
    }
      
    // Print matrix cell value
    document.write(m[i][j] + " ");
      
    // Recursive function to traverse
    // The matrix diagonally
    if (traverseMatrixDiagonally(m, i + 1,
                                    j + 1, row, col))
    {
        return true;
    }
      
    // Recursive function
    // to change diagonal
    if (traverseMatrixDiagonally(m, k1, k2, row, col))
    {
        return true;
    }
      
    return true;
}
  
// Driver Code
  
    // Initialize the 5 x 5 matrix
    let mtrx = [[ 10, 11, 12, 13, 14 ],
                    [ 15, 16, 17, 18, 19 ],
                    [ 20, 21, 22, 23, 24 ],
                    [ 25, 26, 27, 28, 29 ],
                    [ 30, 31, 32, 33, 34 ]];
  
    // Function call
    // for traversing matrix
    traverseMatrixDiagonally(mtrx, 0, 0, 5, 5);
  
  
//This code is contributed by sravan kumar
</script>
Producción

10 16 22 28 34 
15 21 27 33 
11 17 23 29 
20 26 32 
12 18 24 
25 31 
13 19 
30 
14 

Complejidad del tiempo: O(N 2 )

Publicación traducida automáticamente

Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *