Рубрики

Вывести все возможные пути сверху вниз слева направо от матрицы mXn

Проблема состоит в том, чтобы напечатать все возможные пути сверху вниз слева направо от матрицы mXn с ограничениями, которые из каждой ячейки вы можете перемещать только вправо или вниз .

Примеры :

Input : 1 2 3
        4 5 6
Output : 1 4 5 6
         1 2 5 6
         1 2 3 6

Input : 1 2 
        3 4
Output : 1 2 4
         1 3 4

Алгоритм является простым рекурсивным алгоритмом: сначала из каждой ячейки выведите все пути, спускаясь вниз, а затем напечатайте все пути, следуя направо. Сделайте это рекурсивно для каждой обнаруженной ячейки.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// Программа CPP для печати всех возможных путей из
// сверху вниз слева направо от матрицы mXn
#include<iostream>

  

using namespace std;

  
/ * mat: указатель на начало матрицы mXn

   i, j: текущая позиция робота (для первого вызова используйте 0,0)

   m, n: размеры заданной матрицы

   pi: следующий индекс, который будет храниться в массиве путей

   * path [0..pi-1]: путь, пройденный роботом до сих пор (массив для хранения

                  путь должен иметь место как минимум для m + n элементов) * /

void printAllPathsUtil(int *mat, int i, int j, int m, int n, int *path, int pi)

{

    // Достигнем дна матрицы, чтобы мы остались с

    // единственная возможность двигаться вправо

    if (i == m - 1)

    {

        for (int k = j; k < n; k++)

            path[pi + k - j] = *((mat + i*n) + k);

        for (int l = 0; l < pi + n - j; l++)

            cout << path[l] << " ";

        cout << endl;

        return;

    }

  

    // Достигли правого угла матрицы, с которой мы остались

    // только нисходящее движение.

    if (j == n - 1)

    {

        for (int k = i; k < m; k++)

            path[pi + k - i] = *((mat + k*n) + j);

        for (int l = 0; l < pi + m - i; l++)

            cout << path[l] << " ";

        cout << endl;

        return;

    }

  

    // Добавить текущую ячейку к генерируемому пути

    path[pi] = *((mat + i*n) + j);

  

    // Распечатать все пути, которые возможны после перемещения вниз

    printAllPathsUtil(mat, i+1, j, m, n, path, pi + 1);

  

    // Распечатать все пути, которые возможны после движения вправо

    printAllPathsUtil(mat, i, j+1, m, n, path, pi + 1);

  

    // Распечатать все пути, которые возможны после перемещения по диагонали

    // printAllPathsUtil (mat, i + 1, j + 1, m, n, path, pi + 1);

}

  
// Основная функция, которая печатает все пути сверху вниз слева направо
// в матрице 'mat' размера mXn

void printAllPaths(int *mat, int m, int n)

{

    int *path = new int[m+n];

    printAllPathsUtil(mat, 0, 0, m, n, path, 0);

}

  
// Программа драйвера для тестирования abve функций

int main()

{

    int mat[2][3] = { {1, 2, 3}, {4, 5, 6} };

    printAllPaths(*mat, 2, 3);

    return 0;

}

Джава

// Java-программа для печати всех возможных путей из
// сверху вниз слева направо от матрицы mXn

public class MatrixTraversal 

{

  

  

    / * mat: указатель на начало матрицы mXn

   i, j: текущая позиция робота (для первого вызова используйте 0,0)

   m, n: размеры заданной матрицы

   pi: следующий индекс, который будет храниться в массиве путей

   * path [0..pi-1]: путь, пройденный роботом до сих пор (массив для хранения

                  путь должен иметь место как минимум для m + n элементов) * /

    private static void printMatrix(int mat[][], int m, int n,

                                    int i, int j, int path[], int idx)

    {

        path[idx] = mat[i][j];

          

         // Достигнем дна матрицы, чтобы мы остались с

        // единственная возможность двигаться вправо

        if (i == m - 1

        {

            for (int k = j + 1; k < n; k++)

            {

                path[idx + k - j] = mat[i][k];

            }

            for (int l = 0; l < idx + n - j; l++) 

            {

                System.out.print(path[l] + " ");

            }

            System.out.println();

            return;

        }

          

        // Достигли правого угла матрицы, с которой мы остались

        // только нисходящее движение.

        if (j == n - 1

        {

            for (int k = i + 1; k < m; k++) 

            {

                path[idx + k - i] = mat[k][j];

            }

            for (int l = 0; l < idx + m - i; l++) 

            {

                System.out.print(path[l] + " ");

            }

            System.out.println();

            return;

        }

        // Распечатать все пути, которые возможны после перемещения вниз

        printMatrix(mat, m, n, i + 1, j, path, idx + 1);

  

         // Распечатать все пути, которые возможны после движения вправо

        printMatrix(mat, m, n, i, j + 1, path, idx + 1);

    }

      

    // Код драйвера

    public static void main(String[] args) 

    {

        int m = 2;

        int n = 3;

        int mat[][] = { { 1, 2, 3 }, 

                        { 4, 5, 6 } };

        int maxLengthOfPath = m + n - 1;

        printMatrix(mat, m, n, 0, 0, new int[maxLengthOfPath], 0);

    }

}

python3

# Программа Python3 для печати всех возможных путей из
# сверху слева внизу справа от матрицы mXn

  
«»»
/ * mat: указатель на начало матрицы mXn
i, j: текущая позиция робота

     (Для первого звонка используйте 0, 0)

m, n: размеры заданной матрицы
pi: следующий индекс, который будет храниться в массиве путей
* путь [0..pi-1]: путь, пройденный роботом до сих пор

                (Массив для удержания пути надо иметь

                 пространство минимум для m + n элементов) * /

«»»

def printAllPathsUtil(mat, i, j, m, n, path, pi):

  

    # Достигнуто дно матрицы

    # так что у нас остался только вариант двигаться вправо

    if (i == m - 1):

        for k in range(j, n):

            path[pi + k - j] = mat[i][k]

  

        for l in range(pi + n - j):

            print(path[l], end = " ")

        print()

        return

  

    # Достигнут правый угол матрицы

    # у нас осталось только движение вниз.

    if (j == n - 1):

  

        for k in range(i, m):

            path[pi + k - i] = mat[k][j]

  

        for l in range(pi + m - i):

            print(path[l], end = " ")

        print()

        return

  

    # Добавить текущую ячейку

    # к генерируемому пути

    path[pi] = mat[i][j]

  

    # Распечатать все пути

    # которые возможны после съезда

    printAllPathsUtil(mat, i + 1, j, m, n, path, pi + 1)

  

    # Распечатать все пути

    # которые возможны после движения вправо

    printAllPathsUtil(mat, i, j + 1, m, n, path, pi + 1)

  

    # Распечатать все пути

    # которые возможны после перемещения по диагонали

    # printAllPathsUtil (mat, i + 1, j + 1, m, n, path, pi + 1);

  
# Основная функция, которая печатает все пути
# сверху слева внизу справа
# в матрице 'mat' размера mXn

def printAllPaths(mat, m, n):

  

    path = [0 for i in range(m + n)]

    printAllPathsUtil(mat, 0, 0, m, n, path, 0)

  
Код водителя

mat = [[1, 2, 3], 

       [4, 5, 6]]

  

printAllPaths(mat, 2, 3)

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # программа для печати всех возможных путей из
// сверху вниз слева направо от матрицы mXn

using System;

      

public class MatrixTraversal 

{

  

  

    / * mat: указатель на начало матрицы mXn

i, j: текущая позиция робота (для первого вызова используйте 0,0)
m, n: размеры заданной матрицы
pi: следующий индекс, который будет храниться в массиве путей
* path [0..pi-1]: путь, пройденный роботом до сих пор (массив для хранения

                путь должен иметь место как минимум для m + n элементов) * /

    private static void printMatrix(int [,]mat, int m, int n,

                                    int i, int j, int []path, int idx)

    {

        path[idx] = mat[i,j];

          

        // Достигнем дна матрицы, чтобы мы остались с

        // единственная возможность двигаться вправо

        if (i == m - 1) 

        {

            for (int k = j + 1; k < n; k++)

            {

                path[idx + k - j] = mat[i,k];

            }

            for (int l = 0; l < idx + n - j; l++) 

            {

                Console.Write(path[l] + " ");

            }

            Console.WriteLine();

            return;

        }

          

        // Достигли правого угла матрицы, с которой мы остались

        // только нисходящее движение.

        if (j == n - 1) 

        {

            for (int k = i + 1; k < m; k++) 

            {

                path[idx + k - i] = mat[k,j];

            }

            for (int l = 0; l < idx + m - i; l++) 

            {

                Console.Write(path[l] + " ");

            }

            Console.WriteLine();

            return;

        }

          

        // Распечатать все пути, которые возможны после перемещения вниз

        printMatrix(mat, m, n, i + 1, j, path, idx + 1);

  

        // Распечатать все пути, которые возможны после движения вправо

        printMatrix(mat, m, n, i, j + 1, path, idx + 1);

    }

      

    // Код драйвера

    public static void Main(String[] args) 

    {

        int m = 2;

        int n = 3;

        int [,]mat = { { 1, 2, 3 }, 

                        { 4, 5, 6 } };

        int maxLengthOfPath = m + n - 1;

        printMatrix(mat, m, n, 0, 0, new int[maxLengthOfPath], 0);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

1 4 5 6
1 2 5 6
1 2 3 6

Обратите внимание, что в приведенном выше коде последняя строка printAllPathsUtil () закомментирована. Если мы раскомментируем эту строку, мы получим все пути сверху вниз слева направо от матрицы nXm, если диагональные перемещения также разрешены. А также, если перемещение в некоторые ячейки не разрешено, то тот же код можно улучшить, передав массив ограничений в вышеуказанную функцию и оставив его в качестве упражнения.

Эта статья предоставлена Hariprasad NG . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Реализация Python

# Программа Python3 для печати всех возможных путей из
# сверху слева внизу справа от матрицы mXn

allPaths = []

def findPaths(maze,m,n):

    path = [0 for d in range(m+n-1)]

    findPathsUtil(maze,m,n,0,0,path,0)

      

def findPathsUtil(maze,m,n,i,j,path,indx):

    global allPaths

    # если мы достигнем дна лабиринта, мы можем двигаться только вправо

    if i==m-1:

        for k in range(j,n):

            # Path.append (лабиринт [I] [K])

            path[indx+k-j] = maze[i][k]

        # если мы попали в этот блок, это означает, что один путь завершен.

        # Добавить его в список путей и распечатать

        print(path)

        allPaths.append(path)

        return

    # если мы достигнем самого правого угла, мы можем двигаться только вниз

    if j == n-1:

        for k in range(i,m):

            path[indx+k-i] = maze[k][j]

          # Path.append (лабиринтный [J] [K])

        # если мы попали в этот блок, это означает, что один путь завершен.

        # Добавить его в список путей и распечатать

        print(path)

        allPaths.append(path)

        return

      

    # добавить текущий элемент в список путей

    # Path.append (лабиринт [I] [J])

    path[indx] = maze[i][j]

      

    # двигаться вниз в направлении y и рекурсивно вызывать findPathsUtil

    findPathsUtil(maze, m, n, i+1, j, path, indx+1)

      

    # двигаться вниз в направлении y и рекурсивно вызывать findPathsUtil

    findPathsUtil(maze, m, n, i, j+1, path, indx+1)

  

if __name__ == '__main__':

    maze = [[1,2,3],

            [4,5,6],

            [7,8,9]]

    findPaths(maze,3,3)

    #print (allPaths)

Выход:

[1, 4, 7, 8, 9]
[1, 4, 5, 8, 9]
[1, 4, 5, 6, 9]
[1, 2, 5, 8, 9]
[1, 2, 5, 6, 9]
[1, 2, 3, 6, 9]

Рекомендуемые посты:

Вывести все возможные пути сверху вниз слева направо от матрицы mXn

0.00 (0%) 0 votes