Рубрики

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

Учитывая матрицу матрицы mxn, нам нужно вывести все те ячейки, в которых сумма подматрицы, закончившейся в этой ячейке, и подматрицы, начинающейся в этой ячейке, равна оставшимся элементам. Для лучшего понимания смотрите диаграмму ниже,

Примеры :

Input : mat[][] = {1, 2, 3, 5,
                   4, 1, 0, 2,
                   0, 1, 2, 0,
                   7, 1, 1, 0};
Output : (1, 1), (2, 2)      

In above matrix, cell (1, 1) and cell (2, 2)
are our required cells because,
For cell (1, 1), sum of red and green areas is same
1+2+4+1+0+2+1+2+0+1+1+0 = 3+5+0+7        
Same is true for cell (2, 2)
1+2+3+4+1+0+0+1+2+0+1+0 = 5+2+7+1    

We need to print all blue boundary cells for 
which sum of red area is equal to green area.

Сначала мы строим вспомогательные подматрицы, аналогичные статье.

Построим две матрицы sum [] [] и sumr [] [] так, чтобы sum [i] [j] обозначала сумму подматрицы от mat [0] [0] до mat [i] [j]. И sumr для хранения суммы до последних индексов, т.е. sumr [i] [j] обозначает сумму подматрицы , mat [i] [j] — mat [m — 1] [n — 1].
Теперь мы можем использовать вышеупомянутые матрицы для решения этой проблемы. Красная область, показанная на приведенной выше диаграмме, может быть вычислена путем добавления соответствующих ячеек из матриц суммы и суммы, так как mat [i] [j] учитывается дважды, при вычислении этой суммы мы вычтем ее один раз. чтобы получить сумму красной области. Получить сумму оставшегося элемента, зеленой части, довольно просто, мы просто вычтем сумму красной части из общей суммы данной матрицы.
Таким образом, чтобы проверить, удовлетворяет ли конкретная ячейка заданному условию, мы вычислим сумму красной части, как описано выше, и сравним ее с общей суммой матрицы. Если эта сумма равна половине общей суммы, текущая ячейка удовлетворяет условию и, следовательно, является кандидатом на результат.

C / C ++

// C ++ программа для печати ячеек с одинаковым прямоугольником
// сумма по диагонали
#include <bits/stdc++.h>

using namespace std;

#define R 4
#define C 4

  
// Метод печатает индекс ячейки с прямоугольной суммой
// то же самое в простой диагонали и другой диагонали

void printCellWithSameRectangularArea(int mat[R][C],

                                     int m, int n)

{

    / * sum [i] [j] обозначает сумму подматрицы, mat [0] [0]

       чтобы мат [I] [J]

       sumr [i] [j] обозначает сумму подматрицы, mat [i] [j]

       на мат [м - 1] [п - 1] * /

    int sum[m][n], sumr[m][n];

  

    // Инициализируем обе матрицы суммы по mat

    int totalSum = 0;

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

    {

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

        {

            sumr[i][j] = sum[i][j] = mat[i][j];

            totalSum += mat[i][j];

        }

    }

  

    // обновляем первый и последний ряд отдельно

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

    {

        sum[i][0] += sum[i-1][0];

        sumr[m-i-1][n-1] += sumr[m-i][n-1];

    }

  

    // обновляем первый и последний столбец отдельно

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

    {

        sum[0][j] += sum[0][j-1];

        sumr[m-1][n-j-1] += sumr[m-1][n-j];

    }

  

    // обновление индексов суммы и суммы по соседним индексам

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

    {

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

        {

            sum[i][j] += sum[i-1][j] + sum[i][j-1] -

                                      sum[i-1][j-1];

            sumr[m-i-1][n-j-1] += sumr[m-i][n-j-1] +

                                  sumr[m-i-1][n-j] -

                                  sumr[m-i][n-j];

        }

    }

  

    // Раскомментируем код ниже для вывода суммы и обратной суммы

    // матрица

    / *

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            cout << endl;

        }

        cout << endl;

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            cout << endl;

        }

        cout << endl; * /

  

    / * выводим все те индексы, при которых сумма простейшей диагонали

       прямоугольники - это половина общей суммы матрицы * /

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

    {

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

        {

            int mainDiagRectangleSum = sum[i][j] + sumr[i][j] -

                                                   mat[i][j];

            if (totalSum == 2 * mainDiagRectangleSum)

                cout << "(" << i << ", " << j << ")" << endl;

        }

    }

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int mat[R][C] =

    {

        1, 2, 3, 5,

        4, 1, 0, 2,

        0, 1, 2, 0,

        7, 1, 1, 0

    };

  

    printCellWithSameRectangularArea(mat, R, C);

  

    return 0;

}

Джава

// Java-программа для печати ячеек с
// та же прямоугольная сумма по диагонали

  

class GFG {

      

static final int R = 4;

static final int C = 4;

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

static void printCellWithSameRectangularArea(int mat[][], 

                                             int m, int n) 

{

    / * sum [i] [j] обозначает сумму подматрицы, mat [0] [0]

    чтобы мат [I] [J]

    sumr [i] [j] обозначает сумму подматрицы, mat [i] [j]

    на мат [м - 1] [п - 1] * /

    int sum[][] = new int[m][n];

    int sumr[][] = new int[m][n];

  

    // Инициализируем обе матрицы суммы по mat

    int totalSum = 0;

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

    for (int j = 0; j < n; j++) {

        sumr[i][j] = sum[i][j] = mat[i][j];

        totalSum += mat[i][j];

    }

    }

  

    // обновляем первый и последний ряд отдельно

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

    sum[i][0] += sum[i - 1][0];

    sumr[m - i - 1][n - 1] += sumr[m - i][n - 1];

    }

  

    // обновляем первый и последний столбец отдельно

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

    sum[0][j] += sum[0][j - 1];

    sumr[m - 1][n - j - 1] += sumr[m - 1][n - j];

    }

  

    // обновление индексов суммы и суммы по соседним индексам

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

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

        sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - 

                                     sum[i - 1][j - 1];

        sumr[m - i - 1][n - j - 1] += sumr[m - i][n - j - 1] +

                                      sumr[m - i - 1][n - j] -

                                      sumr[m - i][n - j];

    }

    }

  

    // Раскомментируем код ниже для вывода суммы и обратной суммы

    // матрица

    / *

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            System.out.println ();

        }

        System.out.println ();

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            System.out.println ();

        }

        System.out.println (); * /

  

    / * выводим все те индексы, при которых сумма простейшей диагонали

    прямоугольники - это половина общей суммы матрицы * /

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

    for (int j = 0; j < n; j++) {

        int mainDiagRectangleSum = sum[i][j] + 

                       sumr[i][j] - mat[i][j];

        if (totalSum == 2 * mainDiagRectangleSum)

        System.out.println("(" + i + ", " + j + ")");

    }

    }

}

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

public static void main(String[] args)

{

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

                   {4, 1, 0, 2}, 

                   {0, 1, 2, 0}, 

                   {7, 1, 1, 0}};

  

    printCellWithSameRectangularArea(mat, R, C);

}
}

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

питон

# Программа Python для печати ячеек с одинаковым прямоугольником
# сумма по диагонали
# R 4
# C 4

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

def printCellWithSameRectangularArea(mat, m, n):

    # sum [i] [j] обозначает сумму подматрицы, mat [0] [0]

    # мату [i] [j]

    # sumr [i] [j] обозначает сумму подматрицы, mat [i] [j]

    # в мат [м - 1] [п - 1]

    sum = [[0 for i in range(m)]for j in range(n)]

    sumr = [[0 for i in range(m)]for j in range(n)]

   

    # Инициализировать обе матрицы сумм матом

    totalSum = 0

    for i in range(m):

        for j in range(n):

            sumr[i][j] = sum[i][j] = mat[i][j];

            totalSum += mat[i][j]

   

    # обновление первой и последней строки отдельно

    for i in range(1,m):

        sum[i][0] += sum[i-1][0]

        sumr[m-i-1][n-1] += sumr[m-i][n-1]

   

    # обновление первого и последнего столбца отдельно

    for j in range(1,n):

        sum[0][j] += sum[0][j-1];

        sumr[m-1][n-j-1] += sumr[m-1][n-j]

   

    # обновление индексов суммы и суммы по соседним индексам

    for i in range(1,m):

        for j in range(1,n):

            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]

            sumr[m-i-1][n-j-1] += sumr[m-i][n-j-1] + sumr[m-i-1][n-j] - sumr[m-i][n-j]

   

    # Раскомментируйте ниже код для вывода суммы и обратной суммы

    # матрица

   

    # вывести все те индексы, при которых сумма простейшей диагонали

    # Прямоугольники - это половина общей суммы матрицы

    for i in range(m):

        for j in range(n):

            mainDiagRectangleSum = sum[i][j] + sumr[i][j] - mat[i][j]

            if (totalSum == 2 * mainDiagRectangleSum):

                print "(",

                print i,

                print ",",

                print j,

                print ")",

   
# Код драйвера для тестирования вышеуказанных методов

mat =[[1, 2, 3, 5,],

     [4, 1, 0, 2,],

     [0, 1, 2, 0],

     [7, 1, 1, 0]]

printCellWithSameRectangularArea(mat, 4, 4)

  
# Предоставлено Afzal

C #

// C # программа для печати ячеек с
// та же прямоугольная сумма по диагонали

using System;

  

class GFG {

      

static int R = 4;

static int C = 4;

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

static void printCellWithSameRectangularArea(int [,]mat, 

                                             int m, int n) 

{

    / * sum [i] [j] обозначает сумму

       матрица, мат [0] [0] в мат [i] [j]

       sumr [i] [j] обозначает сумму подматрицы,

       mat [i] [j] to mat [m - 1] [n - 1] * /

    int [,]sum = new int[m, n];

    int [,]sumr = new int[m, n];

  

    // Инициализируем обе матрицы суммы по mat

    int totalSum = 0;

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

    for (int j = 0; j < n; j++) {

        sumr[i, j] = sum[i, j] = mat[i, j];

        totalSum += mat[i, j];

    }

    }

  

    // обновляем первый и последний ряд отдельно

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

    {

    sum[i, 0] += sum[i - 1, 0];

    sumr[m - i - 1, n - 1] += sumr[m - i, n - 1];

    }

  

    // обновляем первый и последний столбец отдельно

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

    {

    sum[0,j] += sum[0,j - 1];

    sumr[m - 1,n - j - 1] += sumr[m - 1,n - j];

    }

  

    // обновление индексов суммы и суммы по соседним индексам

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

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

        sum[i,j] += sum[i - 1,j] + sum[i,j - 1] - 

                                   sum[i - 1,j - 1];

        sumr[m - i - 1,n - j - 1] += sumr[m - i,n - j - 1] +

                                     sumr[m - i - 1,n - j] -

                                     sumr[m - i,n - j];

    }

    }

  

    // Раскомментируем код ниже для вывода суммы и обратной суммы

    // матрица

    / *

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            System.out.println ();

        }

        System.out.println ();

        для (int i = 0; i <m; i ++)

        {

            для (int j = 0; j <n; j ++)

            {

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

            }

            System.out.println ();

        }

        System.out.println (); * /

  

    / * выводим все те индексы, по которым сумма

       простых диагональных прямоугольников - половина

       от общей суммы матрицы * /

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

    for (int j = 0; j < n; j++) {

        int mainDiagRectangleSum = sum[i,j] + 

                    sumr[i,j] - mat[i,j];

                      

        if (totalSum == 2 * mainDiagRectangleSum)

        Console.WriteLine("(" + i + ", " + j + ")");

    }

    }

}

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

public static void Main()

{

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

                  {4, 1, 0, 2}, 

                  {0, 1, 2, 0}, 

                  {7, 1, 1, 0}};

  

    printCellWithSameRectangularArea(mat, R, C);

}
}

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


Выход:

(1, 1)
(2, 2)

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes