Распечатать матрицу после применения операций приращения в M диапазонах

Опубликовано: 5 Января, 2022

Для двумерной матрицы mat [] [] размера N * N изначально все элементы матрицы равны 0 . Необходимо выполнить ряд запросов (M диапазонов) для матрицы, где каждый запрос состоит из четырех целых чисел X1 , Y1 , X2 и Y2 , задача состоит в том, чтобы добавить 1 ко всем ячейкам между mat [X1] [Y1] и mat. [X2] [Y2] (включая оба) и в конце распечатать содержимое обновленной матрицы.

Примеры:

Input: N = 2, q[][] = { { 0, 0, 1, 1 }, { 0, 0, 0, 1 } }
Output:
2 2
1 1
After 1st query: mat[][] = { {1, 1}, {1, 1} }
After 2nd query: mat[][] = { {2, 2}, {1, 1} }
Input: N = 5, q[][] = { { 0, 0, 1, 2 }, { 1, 2, 3, 4 }, { 1, 4, 3, 4 } }
Output:
1 1 1 1 1
1 1 2 1 2
2 2 2 2 2
2 2 2 2 2
0 0 0 0 0

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: для каждого запроса (X1, Y1) представляет верхнюю левую ячейку подматрицы, а (X2, Y2) представляет нижнюю правую ячейку подматрицы. Для каждой верхней левой ячейки прибавьте 1 к верхнему левому элементу и вычтите 1 из элемента рядом с нижней правой ячейкой (если есть).
Затем поддерживайте текущую сумму всех элементов из исходной (теперь измененной) матрицы, и при каждом добавлении текущая сумма является элементом (обновленным) в текущей позиции.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include<bits/stdc++.h>
 using namespace std;
 
// Function to update and print the
 // matrix after performing queries
 void updateMatrix( int n, int q[3][4])
 {
    int i, j;
    int mat[n][n];
    for ( int i = 0; i < n; i++)
    for ( int j = 0; j < n; j++)
    mat[i][j] = 0;
    for (i = 0; i < 3; i++)
    {
        int X1 = q[i][0];
        int Y1 = q[i][1];
        int X2 = q[i][2];
        int Y2 = q[i][3];
 
        // Add 1 to the first element of
        // the sub-matrix
        mat[X1][Y1]++;
 
        // If there is an element after the
        // last element of the sub-matrix
        // then decrement it by 1
        if (Y2 + 1 < n)
            mat[X2][Y2 + 1]--;
        else if (X2 + 1 < n)
            mat[X2 + 1][0]--;
    }
 
    // Calculate the running sum
    int sum = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            sum += mat[i][j];
 
            // Print the updated element
            cout << sum << " " ;
        }
 
        // Next line
        cout << endl;
    }
 }
 
// Driver code
 int main()
 {
 
    // Size of the matrix
    int n = 5;
     
 
    // Queries
    int q[3][4] = {{ 0, 0, 1, 2 },
                   { 1, 2, 3, 4 },
                   { 1, 4, 3, 4 }};
 
    updateMatrix(n, q);
    return 0;
 }
 
// This code is contributed by chandan_jnu

Джава

 // Java implementation of the approach
 public class GFG {
 
    // Function to update and print the matrix
    // after performing queries
    static void updateMatrix( int n, int q[][], int mat[][])
    {
        int i, j;
        for (i = 0 ; i < q.length; i++) {
            int X1 = q[i][ 0 ];
            int Y1 = q[i][ 1 ];
            int X2 = q[i][ 2 ];
            int Y2 = q[i][ 3 ];
 
            // Add 1 to the first element of the sub-matrix
            mat[X1][Y1]++;
 
            // If there is an element after the last element
            // of the sub-matrix then decrement it by 1
            if (Y2 + 1 < n)
                mat[X2][Y2 + 1 ]--;
            else if (X2 + 1 < n)
                mat[X2 + 1 ][ 0 ]--;
        }
 
        // Calculate the running sum
        int sum = 0 ;
        for (i = 0 ; i < n; i++) {
            for (j = 0 ; j < n; j++) {
                sum += mat[i][j];
 
                // Print the updated element
                System.out.print(sum + " " );
            }
 
            // Next line
            System.out.println();
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Size of the matrix
        int n = 5 ;
        int mat[][] = new int [n][n];
 
        // Queries
        int q[][] = { { 0 , 0 , 1 , 2 },
                      { 1 , 2 , 3 , 4 },
                      { 1 , 4 , 3 , 4 } };
 
        updateMatrix(n, q, mat);
    }
 }

C #

 // C# implementation of the above approach
 
using System;
 
public class GFG {
 
    // Function to update and print the matrix
    // after performing queries
    static void updateMatrix( int n, int [,]q, int [,]mat)
    {
        int i, j;
        for (i = 0; i < q.GetLength(0); i++) {
            int X1 = q[i,0];
            int Y1 = q[i,1];
            int X2 = q[i,2];
            int Y2 = q[i,3];
 
            // Add 1 to the first element of the sub-matrix
            mat[X1,Y1]++;
 
            // If there is an element after the last element
            // of the sub-matrix then decrement it by 1
            if (Y2 + 1 < n)
                mat[X2,Y2 + 1]--;
            else if (X2 + 1 < n)
                mat[X2 + 1,0]--;
        }
 
        // Calculate the running sum
        int sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                sum += mat[i,j];
 
                // Print the updated element
                Console.Write(sum + " " );
            }
 
            // Next line
            Console.WriteLine();
        }
    }
 
    // Driver code
    public static void Main()
    {
 
        // Size of the matrix
        int n = 5;
        int [,]mat = new int [n,n];
 
        // Queries
        int [,]q = { { 0, 0, 1, 2 },
                    { 1, 2, 3, 4 },
                    { 1, 4, 3, 4 } };
 
        updateMatrix(n, q, mat);
    }
    // This code is contributed by Ryuga
 }

Python3

 # Python 3 implementation of the approach
 
# Function to update and print the matrix
 # after performing queries
 def updateMatrix(n, q, mat):
         
    for i in range ( 0 , len (q)):
            X1 = q[i][ 0 ];
            Y1 = q[i][ 1 ];
            X2 = q[i][ 2 ];
            Y2 = q[i][ 3 ];
 
            # Add 1 to the first element of
            # the sub-matrix
            mat[X1][Y1] = mat[X1][Y1] + 1 ;
 
            # If there is an element after the
            # last element of the sub-matrix
            # then decrement it by 1
            if (Y2 + 1 < n):
                mat[X2][Y2 + 1 ] = mat[X2][Y2 + 1 ] - 1 ;
            elif (X2 + 1 < n):
                mat[X2 + 1 ][ 0 ] = mat[X2 + 1 ][ 0 ] - 1 ;
 
    # Calculate the running sum
    sum = 0 ;
    for i in range ( 0 , n):
        for j in range ( 0 , n):
            sum = sum + mat[i][j];
 
            # Print the updated element
            print ( sum , end = ' ' );
             
        # Next line
        print ( " " );
         
# Driver code
 
# Size of the matrix
 n = 5 ;
 mat = [[ 0 for i in range (n)]
          for i in range (n)];
 
# Queries
 q = [[ 0 , 0 , 1 , 2 ],
     [ 1 , 2 , 3 , 4 ],
     [ 1 , 4 , 3 , 4 ]];
 
updateMatrix(n, q, mat);
     
# This code is contributed
 # by Shivi_Aggarwal

PHP

 <?php
 // PHP implementation of the approach
 
// Function to update and print the
 // matrix after performing queries
 function updateMatrix( $n , $q , $mat )
 {
    for ( $i = 0; $i < sizeof( $q ); $i ++)
    {
        $X1 = $q [ $i ][0];
        $Y1 = $q [ $i ][1];
        $X2 = $q [ $i ][2];
        $Y2 = $q [ $i ][3];
 
        // Add 1 to the first element of
        // the sub-matrix
        $mat [ $X1 ][ $Y1 ]++;
 
        // If there is an element after the last
        // element of the sub-matrix then decrement
        // it by 1
        if ( $Y2 + 1 < $n )
            $mat [ $X2 ][ $Y2 + 1]--;
        else if ( $X2 + 1 < $n )
            $mat [ $X2 + 1][0]--;
    }
 
    // Calculate the running sum
    $sum = 0;
    for ( $i = 0; $i < $n ; $i ++)
    {
        for ( $j = 0; $j < $n ; $j ++)
        {
            $sum += $mat [ $i ][ $j ];
 
            // Print the updated element
            echo ( $sum . " " );
        }
 
        // Next line
        echo ( "
" );
    }
 }
 
// Driver code
 
// Size of the matrix
 $n = 5;
 $mat = array_fill (0, $n ,
       array_fill (0, $n , 0));
 
// Queries
 $q = array ( array ( 0, 0, 1, 2 ),
           array ( 1, 2, 3, 4 ),
           array ( 1, 4, 3, 4 ));
 
updateMatrix( $n , $q , $mat );
 
// This code is contributed by chandan_jnu
 ?>

Выход:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы

Распечатать матрицу после применения операций приращения в M диапазонах

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Джава

C #

Python3

PHP

РЕКОМЕНДУЕМЫЕ СТАТЬИ