Рубрики

Зигзагообразный (или диагональный) обход матрицы

Для заданной 2D матрицы выведите все элементы данной матрицы в диагональном порядке. Например, рассмотрим следующую матрицу ввода 5 X 4.

    1     2     3     4
    5     6     7     8
    9    10    11    12
   13    14    15    16
   17    18    19    20

Диагональная печать вышеуказанной матрицы

    1
    5     2
    9     6     3
   13    10     7     4
   17    14    11     8
   18    15    12
   19    16
   20

Другой пример:

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Ниже приведен код для диагональной печати.

Диагональная печать данной матрицы «matrix [ROW] [COL]» всегда имеет строки «ROW + COL — 1» на выходе.

C ++

#include <stdio.h>
#include <stdlib.h>

  
#define ROW 5
#define COL 4

  
// Утилита для поиска минимума двух целых чисел

int minu(int a, int b)

{ return (a < b)? a: b; }

  
// Полезная функция, чтобы найти минимум трех целых

int min(int a, int b, int c)

{ return minu(minu(a, b), c);}

  
// Полезная функция, чтобы найти максимум двух целых

int max(int a, int b)

{ return (a > b)? a: b; }

  
// Основная функция, которая печатает данную матрицу в диагональном порядке

void diagonalOrder(int matrix[][COL])

{

    // На выходе будут строки ROW + COL-1

    for (int line=1; line<=(ROW + COL -1); line++)

    {

        / * Получить индекс столбца первого элемента в этой строке вывода.

           Индекс равен 0 для первых строк ROW и строки - ROW для остальных

           линии * /

        int start_col =  max(0, line-ROW);

  

        / * Получить количество элементов в этой строке. Количество элементов

           равно минимуму номера строки, COL-start_col и ROW * /

         int count = min(line, (COL-start_col), ROW);

  

        / * Распечатать элементы этой строки * /

        for (int j=0; j<count; j++)

            printf("%5d ", matrix[minu(ROW, line)-j-1][start_col+j]);

  

        / * Печатать элементы следующей диагонали на следующей строке * /

        printf("\n");

    }

}

  
// Утилита для печати матрицы

void printMatrix(int matrix[ROW][COL])

{

    for (int i=0; i< ROW; i++)

    {

        for (int j=0; j<COL; j++)

            printf("%5d ", matrix[i][j]);

        printf("\n");

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int M[ROW][COL] = {{1, 2, 3, 4},

                       {5, 6, 7, 8},

                       {9, 10, 11, 12},

                       {13, 14, 15, 16},

                       {17, 18, 19, 20},

                      };

    printf ("Given matrix is \n");

    printMatrix(M);

  

    printf ("\nDiagonal printing of matrix is \n");

    diagonalOrder(M);

    return 0;

}

Джава

class GFG {

static final int ROW = 5;

static final int COL = 4;

  
// Полезная функция для поиска минимума
// из двух целых

static int min(int a, int b) {

    return (a < b) ? a : b;

    }

  
// Полезная функция для поиска минимума
// из трех целых

static int min(int a, int b, int c) {

    return min(min(a, b), c);

    }

  
// Полезная функция для поиска max
// из двух целых

static int max(int a, int b) { 

    return (a > b) ? a : b;

    }

  
// Основная функция, которая печатает данный
// матрица в диагональном порядке

static void diagonalOrder(int matrix[][]) {

  

    // На выходе будут строки ROW + COL-1

    for (int line = 1; line <= (ROW + COL - 1); line++) {

  

    // Получить индекс столбца первого элемента в этом

    // строка вывода. Индекс равен 0 для первой строки

    // линии и строки - строка для оставшихся строк

    int start_col = max(0, line - ROW);

  

    // Получить количество элементов в этой строке. Счет

    // элементов равно минимуму номера строки,

    // COL-start_col и ROW

    int count = min(line, (COL - start_col), ROW);

  

    // Распечатать элементы этой строки

    for (int j = 0; j < count; j++)

        System.out.print(matrix[min(ROW, line) - j - 1]

                            [start_col + j] + " ");

  

    // Печать элементов следующей диагонали на следующей строке

    System.out.println();

    }

}

  
// Утилита для печати матрицы

static void printMatrix(int matrix[][]) {

    for (int i = 0; i < ROW; i++) {

    for (int j = 0; j < COL; j++)

        System.out.print(matrix[i][j] + " ");

    System.out.print("\n");

    }

}

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

public static void main(String[] args) {

    int M[][] = {

        {1, 2, 3, 4},     {5, 6, 7, 8},     {9, 10, 11, 12},

        {13, 14, 15, 16}, {17, 18, 19, 20},

    };

    System.out.print("Given matrix is \n");

    printMatrix(M);

  

    System.out.print("\nDiagonal printing of matrix is \n");

    diagonalOrder(M);

}
}
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для печати всех элементов
# данной матрицы в диагональном порядке

ROW = 5

COL = 4

  
# Основная функция, которая печатает данные
# матрица в диагональном порядке

def diagonalOrder(matrix) :

      

    # На выходе будут строки ROW + COL-1

    for line in range(1, (ROW + COL)) :

        # Получить индекс столбца первого элемента

        # в этой строке вывода. Индекс 0

        # для первых строк ROW и строки - ROW для

        # оставшиеся строки

        start_col = max(0, line - ROW)

  

        # Получить количество элементов в этой строке.

        # Количество элементов равно

        # минимум номера строки, COL-start_col и ROW

        count = min(line, (COL - start_col), ROW)

  

        # Распечатать элементы этой строки

        for j in range(0, count) :

            print(matrix[min(ROW, line) - j - 1]

                        [start_col + j], end = "\t")

  

        print()

      

      
# Утилита для печати матрицы

def printMatrix(matrix) :

    for i in range(0, ROW) :

        for j in range(0, COL) :

            print(matrix[i][j], end = "\t")

              

        print()

          

  
# Код водителя

M = [ [1, 2, 3, 4],

    [5, 6, 7, 8],

    [9, 10, 11, 12],

    [13, 14, 15, 16],

    [17, 18, 19, 20] ]

print("Given matrix is ")

printMatrix(M)

  

print ("\nDiagonal printing of matrix is ")

diagonalOrder(M)

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для печати всех элементов
// данной матрицы в диагональном порядке

using System;

  

class GFG {

      

    static int ROW = 5;

    static int COL = 4;

  

      

    // Основная функция, которая печатает данный

    // матрица в диагональном порядке

    static void diagonalOrder(int [,]matrix) {

      

        // На выходе будут строки ROW + COL-1

        for (int line = 1; line <= (ROW + COL - 1); line++)

        {

      

            // Получить индекс столбца первого элемента

            // в этой строке вывода. Индекс равен 0

            // для первых строк и строк - строка для

            // оставшиеся строки

            int start_col = Math.Max(0, line - ROW);

          

            // Получить количество элементов в этой строке.

            // количество элементов равно минимуму

            // номер строки, COL-start_col и ROW

            int count = Math.Min(line, Math.Min(

                                  (COL - start_col), ROW));

      

            // Распечатать элементы этой строки

            for (int j = 0; j < count; j++)

                Console.Write(matrix[ Math.Min(ROW, line) 

                            - j - 1, start_col + j] + " ");

          

            // Печать элементов следующей диагонали на следующей строке

            Console.WriteLine();

        }

    }

      

    // Утилита для печати матрицы

    static void printMatrix(int [,]matrix) {

        for (int i = 0; i < ROW; i++) {

            for (int j = 0; j < COL; j++)

                Console.Write(matrix[i,j] + " ");

                  

            Console.WriteLine("\n");

        }

    }

      

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

    public static void Main() {

        int [,]M = {{1, 2, 3, 4},

                    {5, 6, 7, 8},

                    {9, 10, 11, 12},

                    {13, 14, 15, 16}, 

                    {17, 18, 19, 20}};

                      

        Console.Write("Given matrix is \n");

        printMatrix(M);

      

        Console.Write("\nDiagonal printing" 

                     + " of matrix is \n");

                       

        diagonalOrder(M);

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php 
// PHP код для зигзага (или диагонали)
// обход матрицы

$ROW = 5;

$COL = 4;

  
// Основная функция, которая печатает
// заданная матрица в диагональном порядке

function diagonalOrder(&$matrix)

{

    global $ROW, $COL;

      

    // Там будет ROW + COL-1

    // строки в выводе

    for ($line = 1; 

         $line <= ($ROW + $COL - 1); $line++)

    {

        / * Получить индекс столбца первого

           элемент в этой строке вывода.

           Индекс 0 для первых строк ROW

           и строка - строка для оставшихся строк * /

        $start_col = max(0, $line - $ROW);

  

        / * Получить количество элементов в этой строке.

           Количество элементов равно

           минимум номера строки, COL-start_col

           и ROW * /

        $count = min($line, ($COL

                     $start_col), $ROW);

  

        / * Распечатать элементы этой строки * /

        for ($j = 0; $j < $count; $j++)

        {

            echo $matrix[min($ROW, $line) - 

                 $j - 1][$start_col + $j];

            echo "\t";

        }

  

        / * Печать элементов следующего

           диагональ на следующей строке * /

        print("\n");

    }

}

  
// Вспомогательная функция
// напечатать матрицу

function printMatrix(&$matrix)

{

    global $ROW, $COL;

    for ($i = 0; $i < $ROW; $i++)

    {

        for ($j = 0; $j < $COL; $j++)

        {

            echo $matrix[$i][$j] ;

            echo "\t";

        }

        print("\n");

    }

}

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

$M = array(array(1, 2, 3, 4),

           array(5, 6, 7, 8),

           array(9, 10, 11, 12),

           array(13, 14, 15, 16),

           array(17, 18, 19, 20));

echo "Given matrix is \n";

printMatrix($M);

  

printf ("\nDiagonal printing " .

        "of matrix is \n");

diagonalOrder($M);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Given matrix is
    1     2     3     4
    5     6     7     8
    9    10    11    12
   13    14    15    16
   17    18    19    20

Diagonal printing of matrix is
    1
    5     2
    9     6     3
   13    10     7     4
   17    14    11     8
   18    15    12
   19    16
   20

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

Matrix =>       1     2     3     4
                5     6     7     8
                9     10    11   12
                13    14    15   16
                17    18    19   20 
   
Observe the sequence
          1 /  2 /  3 /  4
           / 5  /  6 /  7 /  8
               /  9 / 10 / 11 / 12
                   / 13 / 14 / 15 / 16
                       / 17 / 18 / 19 / 20

C ++

#include<bits/stdc++.h>
#define R 5
#define C 4

using namespace std;

  

bool isValid(int i, int j)

{

    if (i < 0 || i >= R || j >= C || j < 0) return false;

    return true;

}

  

void diagonalOrder(int arr[][C])

{

    / * через цикл for мы выбираем каждый элемент первого столбца

    в качестве отправной точки и печати диагонали, начиная с нее.

    arr [0] [0], arr [1] [0] .... arr [R-1] [0] - все отправные точки * /

    for (int k = 0; k < R; k++)

    {

        cout << arr[k][0] << " ";

        int i = k-1;    // установить индекс строки для следующей точки по диагонали

        int j = 1;        // установить индекс столбца для следующей точки по диагонали

  

        / * Печать по диагонали вверх * /

        while (isValid(i,j))

        {

            cout << arr[i][j] << " ";

            i--;

            j++;    // двигаться в вертикальном направлении

        }

        cout << endl;

    }

  

    / * через цикл for мы выбираем каждый элемент последней строки

       в качестве отправной точки (кроме [0] [c-1] это уже было

       обработано в предыдущем цикле) и выведите диагональ, начиная с нее.

       arr [R-1] [0], arr [R-1] [1] .... arr [R-1] [c-1] - все отправные точки * /

  

    // Примечание: мы начинаем с k = 1 до C-1;

    for (int k = 1; k < C; k++)

    {

        cout << arr[R-1][k] << " ";

        int i = R-2; // установить индекс строки для следующей точки по диагонали

        int j = k+1; // установить индекс столбца для следующей точки по диагонали

  

        / * Печать по диагонали вверх * /

        while (isValid(i,j))

        {

            cout << arr[i][j] << " ";

            i--;

            j++; // двигаться в вертикальном направлении

        }

        cout << endl;

    }

}

  
// Программа драйвера для тестирования выше

int main()

{

  

    int arr[][C] = {{1, 2, 3, 4},

        {5, 6, 7, 8},

        {9, 10, 11, 12},

        {13, 14, 15, 16},

        {17, 18, 19, 20},

    };

    diagonalOrder(arr);

    return 0;

}

Джава

// JAVA-код для зигзага (или диагонали)
// обход матрицы

    

   class GFG{

     

     public static int R,C;

       

     private static void diagonalOrder(int[][] arr) {

           

             / * через этот цикл мы выбираем каждый элемент

             первого столбца в качестве отправной точки и печати

             диагональ, начиная с этого. arr [0] [0], arr [1] [0]

             .... arr [R-1] [0] все начальные точки * /

             for (int k = 0; k < R; k++)

             {

                 System.out.print(arr[k][0] + " ");

                   

                 int i = k - 1;    // установить индекс строки для следующего

                                   // точка по диагонали

                 int j = 1;       // установить индекс столбца для

                                  // следующая точка по диагонали

            

                 / * Печать по диагонали вверх * /

                 while (isValid(i, j))

                 {

                     System.out.print(arr[i][j] + " ");

                       

                     i--;

                     j++;    // двигаться в вертикальном направлении

                 }

                   

                 System.out.println("");

             }

            

             / * через этот цикл мы выбираем каждый элемент

                последней строки в качестве отправной точки (кроме

                [0] [c-1] он уже был обработан в

                предыдущий цикл) и печать диагонали

                начиная с этого. обр [R-1] [0], обр [R-1] [1] ....

                arr [R-1] [c-1] - все отправные точки * /

            

             // Примечание: мы начинаем с k = 1 до C-1;

             for (int k = 1; k < C; k++)

             {

                 System.out.print(arr[R-1][k] + " ");

                   

                 int i = R - 2; // установить индекс строки для следующего

                                // точка по диагонали

                 int j = k + 1; // установить индекс столбца для

                                // следующая точка по диагонали

            

                 / * Печать по диагонали вверх * /

                 while (isValid(i, j))

                 {

                     System.out.print(arr[i][j] + " ");

                       

                     i--;

                     j++; // двигаться в вертикальном направлении

                 }

                   

                 System.out.println("");

             }

         }

              

    public static  boolean isValid(int i, int j)

     {

         if (i < 0 || i >= R || j >= C || j < 0) return false;

         return true;

     }

       

          // программа драйвера для проверки вышеуказанной функции

          public static void main(String[] args) {

              int arr[][] = { {1, 2, 3, 4},

                              {5, 6, 7, 8},

                              {9, 10, 11, 12},

                              {13, 14, 15, 16},

                              {17, 18, 19, 20}, };

                

              R=arr.length;

              C=arr[0].length;

                

              diagonalOrder(arr);

        }

 }

          

    // Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python3 программа для печати всех элементов
# данной матрицы в диагональном порядке

R = 5

C = 4

  

def isValid( i, j) :

    if (i < 0 or i >= R or j >= C or j < 0) :

        return False

    return True

      

  

def diagonalOrder(arr) :

      

    # через это для цикла мы выбираем каждый элемент

    № первого столбца в качестве отправной точки и печати

    # диагональ, начиная с него.

    # arr [0] [0], arr [1] [0] .... arr [R-1] [0]

    # все начальные точки

    for k in range(0, R) :

        print(arr[k][0], end = "  ")

          

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

        i = k - 1 

          

        # установить индекс столбца для следующей точки по диагонали

        j = 1    

  

        # Печать по диагонали вверх

        while (isValid(i, j)) :

            print(arr[i][j], end = "  ")

            i -= 1

            j += 1 # двигаться в вертикальном направлении

          

        print()

  

    # Через это для цикла мы выбираем каждый

    # элемент последней строки в качестве отправной точки

    # (кроме [0] [c-1] это уже было

    # обработано в предыдущем цикле) и распечатать

    # диагональ, начиная с него.

    # arr [R-1] [0], arr [R-1] [1] .... arr [R-1] [c-1]

    # все начальные точки

  

    # Примечание: мы начинаем с k = 1 до C-1;

    for k in range(1, C) :

        print(arr[R-1][k], end = "  ")

          

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

        i = R - 2

          

        # установить индекс столбца для следующей точки по диагонали

        j = k + 1     

  

        # Печать по диагонали вверх

        while (isValid(i, j)) :

            print( arr[i][j], end = "  ")

            i -= 1

            j += 1 # двигаться в вертикальном направлении

          

        print()

          
Код водителя

arr = [ [1, 2, 3, 4],

        [5, 6, 7, 8],

        [9, 10, 11, 12],

        [13, 14, 15, 16],

        [17, 18, 19, 20] ]

diagonalOrder(arr)

  
# Этот код предоставлен Никитой Тивари.

C #

// код C # для зигзага (или диагонали)
// обход матрицы

using System;

  

class GFG

{

public static int R, C;

  

private static void diagonalOrder(int[,] arr) 

{

      

    / * через это для цикла мы

    выберите каждый элемент первого

    столбец в качестве отправной точки и

    печать диагонали, начиная с него.

    обр [0,0], обр [1,0] .... обр [Р-1,0]

    все начальные точки * /

    for (int k = 0; k < R; k++)

    {

        Console.Write(arr[k, 0] + " ");

          

        int i = k - 1;  // установить индекс строки для следующего

                        // точка по диагонали

        int j = 1;    // установить индекс столбца для

                    // следующая точка по диагонали

      

        / * Печать по диагонали вверх * /

        while (isValid(i, j))

        {

            Console.Write(arr[i, j] + " ");

              

            i--;

            j++; // двигаться в вертикальном направлении

        }

          

        Console.Write("\n");

    }

      

    / * через это для цикла мы

        выберите каждый элемент последнего

        строка в качестве отправной точки (кроме

        [0] [c-1] это уже

        были обработаны в предыдущем для

        цикл) и печать по диагонали, начиная

        на него. обр [R-1,0], обр [R-1,1] ....

        arr [R-1, c-1] - все отправные точки * /

      

    // Примечание: мы начинаем с k = 1 до C-1;

    for (int k = 1; k < C; k++)

    {

        Console.Write(arr[R - 1, k] + " ");

          

        int i = R - 2;  // установить индекс строки для следующего

                        // точка по диагонали

        int j = k + 1;  // установить индекс столбца для

                        // следующая точка по диагонали

      

        / * Печать по диагонали вверх * /

        while (isValid(i, j))

        {

            Console.Write(arr[i, j] + " ");

              

            i--;

            j++; // двигаться в вертикальном направлении

        }

          

        Console.Write("\n");

    }

}

      

public static bool isValid(int i, int j)

{

    if (i < 0 || i >= R || 

        j >= C || j < 0) return false;

    return true;

}

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

public static void Main() 

{

    int [,]arr = {{1, 2, 3, 4},

                  {5, 6, 7, 8},

                  {9, 10, 11, 12},

                  {13, 14, 15, 16},

                  {17, 18, 19, 20}};

          

    R = arr.GetLength(0);

    C = arr.GetLength(1);

          

    diagonalOrder(arr);

}
}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// PHP-код для зигзага (или диагонали)
// обход матрицы

define("R", 5); 

define("C", 4); 

  

function isValid($i, $j

    if ($i < 0 || $i >= R || 

        $j >= C || $j < 0) return false; 

    return true; 

  

function diagonalOrder(&$arr

    / * через этот цикл мы выбираем

    каждый элемент первого столбца как

    Начальная точка и диагональ печати

    начиная с этого.

    arr [0] [0], arr [1] [0] .... arr [R-1] [0]

    все начальные точки * /

    for ($k = 0; $k < R; $k++) 

    

        echo $arr[$k][0] . " "

        $i = $k - 1; // установить индекс строки для следующего

                     // точка по диагонали

        $j = 1; // установить индекс столбца для следующего

                // точка по диагонали

  

        / * Печать по диагонали вверх * /

        while (isValid($i,$j)) 

        

            echo $arr[$i][$j] . " "

            $i--; 

            $j++; // двигаться в вертикальном направлении

        

        echo "\n"

    

  

    / * через этот цикл мы выбираем каждый

    элемент последней строки в качестве отправной точки

    (кроме [0] [c-1] это уже было

    обработано в предыдущем цикле) и распечатать

    диагональ, начиная с этого. обр [R-1] [0],

    arr [R-1] [1] .... arr [R-1] [c-1] все

    начальные точки * /

  

    // Примечание: мы начинаем с k = 1 до C-1;

    for ($k = 1; $k < C; $k++) 

    

        echo $arr[R - 1][$k] . " "

        $i = R - 2; // установить индекс строки для следующего

                    // точка по диагонали

        $j = $k + 1; // установить индекс столбца для следующего

                     // точка по диагонали

  

        / * Печать по диагонали вверх * /

        while (isValid($i, $j)) 

        

            echo $arr[$i][$j] . " "

            $i--; 

            $j++; // двигаться в вертикальном направлении

        

        echo "\n";

    

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

$arr = array(array(1, 2, 3, 4), 

             array(5, 6, 7, 8), 

             array(9, 10, 11, 12), 

             array(13, 14, 15, 16), 

             array(17, 18, 19, 20)); 

diagonalOrder($arr); 

  
// Этот код добавлен
// ратбхупендра
?>


Выход:

1
5 2
9 6 3
13 10 7 4
17 14 11 8
18 15 12
19 16
20

Спасибо Гаураву Ахирвару за то, что он предложил этот метод.

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

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

Зигзагообразный (или диагональный) обход матрицы

0.00 (0%) 0 votes