Imprima todas las rutas posibles desde la primera fila hasta la última fila en una array 2D

Dada una array 2D de caracteres con M filas y N columnas. La tarea es imprimir todas las rutas posibles desde arriba (primera fila) hasta abajo (última fila).

Ejemplos:  

Entrada: arr[][] = { 
{‘a’, ‘b’, ‘c’}, 
{‘d’, ‘e’, ​​’f’}, 
{‘g’, ‘h’, ‘i’} } 
Salida: 
adg adh adi aeg aeh aei afg afh afi 
bdg bdh bdi beg beh bei bfg bfh bfi 
cdg cdh cdi ceg ceh cei cfg cfh cfi
Entrada: arr[][] = { 
{‘a’, ‘b’}, 
{ ‘d’, ‘e’}, } 
Salida: 
ad ae 
bd be  

Acercarse:  

1. Este problema se puede resolver usando el recorrido primero en profundidad de una array con una ligera modificación.
2. La modificación aquí es solo iterar a través de las columnas en la array hasta que se alcance la fila de destino.

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

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
void dfs(char inputchar[][2], string res,
                int i, int j, int R, int C)
{
     
    // If the current row index equals to R, it
    // indicates we have reached the bottom of
    // the array and hence we print the result
    if (i == R)
    {
        cout << res << " ";
        return;
    }
 
    res = res + (inputchar[i][j]);
 
    // Iterate over each of the columns
    // in the array
    for (int k = 0; k < C ; k++)
    {
        dfs(inputchar, res, i + 1, k, R, C);
        if (i + 1 == R)
            break;
    }
}
 
// Function to print all the possible paths
void printPaths(char inputchar[][2], int R, int C)
{
    for (int i = 0; i < C; i++)
    {
        dfs(inputchar, "", 0, i, R, C);
        cout<<endl;
    }
         
    /*
    * Depth first traversal of the array
    *
    * @param input array of characters
    * @param res to be printed in console
    * @param i current row index
    * @param j current column index
    * @param R number of rows in the input array
    * @param C number of rows in the output array
    *
*/
}
 
 
// Driver code
int main()
{
     
    char inputchar[][2] = {
            { 'a', 'b' },
            { 'd', 'e' }
            };
             
    int R = sizeof(inputchar)/sizeof(inputchar[0]);
    int C = sizeof(inputchar[0])/sizeof(char);
 
    printPaths(inputchar, R, C);
}
 
// This code is contributed by chitranayal

// Java implementation of the approach
public class GFG {
 
    // Function to print all the possible paths
    private static void printPaths(char[][] input,
                                   int R, int C)
    {
        for (int i = 0; i < C; i++) {
            dfs(input, "", 0, i, R, C);
            System.out.println();
        }
    }
 
    /**
    * Depth first traversal of the array
    *
    * @param input array of characters
    * @param res to be printed in console
    * @param i     current row index
    * @param j     current column index
    * @param R     number of rows in the input array
    * @param C     number of rows in the output array
    */
    private static void dfs(char[][] input, String res,
                            int i, int j, int R, int C)
    {
        // If the current row index equals to R, it
        // indicates we have reached the bottom of
        // the array and hence we print the result
        if (i == R) {
            System.out.print(res + " ");
            return;
        }
 
        res = res + input[i][j];
 
        // Iterate over each of the columns
        // in the array
        for (int k = 0; k < C; k++) {
            dfs(input, res, i + 1, k, R, C);
            if (i + 1 == R) {
                break;
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char[][] input = {
            { 'a', 'b' },
            { 'd', 'e' }
        };
        int R = input.length;
        int C = input[0].length;
        printPaths(input, R, C);
    }
}

# Python3 implementation of the approach
 
# Function to print all the possible paths
def printPaths(inputchar, R, C) :
    for i in range(C) :
        dfs(inputchar, "", 0, i, R, C);
        print()
         
    """
    * Depth first traversal of the array
    *
    * @param input array of characters
    * @param res to be printed in console
    * @param i current row index
    * @param j current column index
    * @param R number of rows in the input array
    * @param C number of rows in the output array
    * """
def dfs(inputchar, res, i, j, R, C) :
     
    # If the current row index equals to R, it
    # indicates we have reached the bottom of
    # the array and hence we print the result
    if (i == R) :
        print(res, end = " ");
        return;
 
    res = res + inputchar[i][j];
 
    # Iterate over each of the columns
    # in the array
    for k in range(C) :
        dfs(inputchar, res, i + 1, k, R, C);
        if (i + 1 == R) :
            break;
 
# Driver code
if __name__ == "__main__" :
     
    inputchar = [
            [ 'a', 'b' ],
            [ 'd', 'e' ]
            ];
             
    R = len(inputchar);
    C = len(inputchar[0]);
     
    printPaths(inputchar, R, C);
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to print all the possible paths
    private static void printPaths(char[,] input,
                                int R, int C)
    {
        for (int i = 0; i < C; i++)
        {
            dfs(input, "", 0, i, R, C);
            Console.WriteLine();
        }
    }
 
    /**
    * Depth first traversal of the array
    *
    * @param input array of characters
    * @param res to be printed in console
    * @param i current row index
    * @param j current column index
    * @param R number of rows in the input array
    * @param C number of rows in the output array
    */
    private static void dfs(char[,] input, string res,
                            int i, int j, int R, int C)
    {
        // If the current row index equals to R, it
        // indicates we have reached the bottom of
        // the array and hence we print the result
        if (i == R)
        {
            Console.Write(res + " ");
            return;
        }
 
        res = res + input[i,j];
 
        // Iterate over each of the columns
        // in the array
        for (int k = 0; k < C; k++)
        {
            dfs(input, res, i + 1, k, R, C);
            if (i + 1 == R)
            {
                break;
            }
        }
    }
 
    // Driver code
    public static void Main()
    {
        char[,] input = {
            { 'a', 'b' },
            { 'd', 'e' }
        };
        int R = input.GetLength(0);
        int C = input.GetLength(1);
        printPaths(input, R, C);
    }
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation of the approach
 
 
    // Function to print all the possible paths
     function printPaths( input , R , C) {
        for (i = 0; i < C; i++) {
            dfs(input, "", 0, i, R, C);
            document.write("<br/>");
        }
    }
 
 
     function dfs( input,  res , i , j , R , C) {
        // If the current row index equals to R, it
        // indicates we have reached the bottom of
        // the array and hence we print the result
        if (i == R) {
            document.write(res + " ");
            return;
        }
 
        res = res + input[i][j];
 
        // Iterate over each of the columns
        // in the array
        for (var k = 0; k < C; k++) {
            dfs(input, res, i + 1, k, R, C);
            if (i + 1 == R) {
                break;
            }
        }
    }
 
    // Driver code
     
        var input = [ [ 'a', 'b' ], [ 'd', 'e' ] ];
        var R = input.length;
        var C = input[0].length;
        printPaths(input, R, C);
 
// This code contributed by Rajput-Ji
</script>

ad ae 
bd be

Complejidad de tiempo: O(R * C) 
Complejidad de espacio: O(1)