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