Окончательная матрица после увеличения всех ячеек заданных подматриц
Опубликовано: 23 Февраля, 2023
Дана матрица размерности N*N , все ячейки которой изначально равны 0. Вам дано Q запросов, каждый из типов {a, b, c, d}, где (a, b) — верхняя левая ячейка, а (c, d ) — нижняя правая ячейка подматрицы, каждую ячейку которой необходимо увеличить на 1. Задача состоит в том, чтобы найти окончательную матрицу после увеличения всех подматриц.
Примеры :
Input: N = 6, Q = 6, queries = { {4, 0, 5, 3}, {0, 0, 3, 4}, {1, 2, 1, 2}, {1, 1, 2, 3}, {0, 0, 3, 1}, {1, 0, 2, 4} }
Output:
2 2 1 1 1 0
3 4 4 3 2 0
3 4 3 3 2 0
2 2 1 1 1 0
1 1 1 1 0 0
1 1 1 1 0 0
Explanation: After incrementing all the sub-matrices of given queries we will get the final output.Input: N = 4, Q = 2, queries = { {0, 0, 3, 3}, {0, 0, 2, 2} }
Output:
2 2 2 1
2 2 2 1
2 2 2 1
1 1 1 1
Explanation: After incrementing all the sub-matrices of given queries we will get the final output.
Подход :
We will be using Difference Array algorithm which is used in 1D array. We will be using this extended algorithm for the 2D matrix. By pre-processing the queries we will be able to get the whole matrix after queries.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Разностный массив D[i] заданного массива A[i] определяется как D[i] = A[i]-A[i-1] (для 0 < i < N ) и D[0] = A[0 ] .
- Мы создадим два одномерных массива, в одном из которых будут храниться обновления строки, а в другом — обновления столбца.
- После обработки запросов мы теперь получим матрицу.
- Для первого элемента строки и столбца выполните A[0] = D[0], а для остальных элементов выполните A[i] = A[i-1] + D[i] . Это будет одинаково реализовано в 2D-матрице для каждой строки и столбца.
- После этого оцените первую строку, и тогда мы сможем получить все элементы, используя приведенную ниже формулу.
матрица[j][i] += матрица[j][i – 1] + строка[j][i] + столбец[j][i].
Ниже приведена реализация описанного выше подхода.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to solve q Queriesvector<vector<int> > solveQueries(int N, vector<vector<int> > Queries){ // Initialize vectors vector<vector<int> > matrix(N + 2, vector<int>(N + 2, 0)); vector<vector<int> > row(N + 2, vector<int>(N + 2, 0)); vector<vector<int> > col(N + 2, vector<int>(N + 2, 0)); // Traverse over the queries for (auto i : Queries) { int a = i[0]; int b = i[1]; int c = i[2]; int d = i[3]; row[a][b]++; row[b]--; col[a][d + 1]--; col[d + 1]++; } // Update row and col vector for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { row[j][i] += row[j - 1][i]; col[j][i] += col[j - 1][i]; } } // Traverse and update matrix vector for (int i = 0; i < N; i++) { matrix[i][0] = row[i][0] + col[i][0]; } for (int i = 1; i <= N; i++) { for (int j = 0; j < N; j++) { matrix[j][i] += matrix[j][i - 1] + row[j][i] + col[j][i]; } } // resultant answer vector vector<vector<int> > res(N, vector<int>(N, 0)); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) res[i][j] = matrix[i][j]; return res;}// function to print resultant matrixvoid printAns(vector<vector<int> >& res){ for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res[0].size(); j++) { cout << res[i][j] << " "; } cout << endl; }}// Driver Codeint main(){ int N = 6; int q = 6; vector<vector<int> > Queries = { { 4, 0, 5, 3 }, { 0, 0, 3, 4 }, { 1, 2, 1, 2 }, { 1, 1, 2, 3 }, { 0, 0, 3, 1 }, { 1, 0, 2, 4 } }; vector<vector<int> > res; res = solveQueries(N, Queries); printAns(res); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG{ // Function to solve q Queries public static int[][] solveQueries(int N, int Queries[][]) { // Initialize arrays int matrix[][] = new int[N + 2][N + 2]; int row[][] = new int[N + 2][N + 2]; int col[][] = new int[N + 2][N + 2]; // Traverse over the queries for (int i[] : Queries) { int a = i[0]; int b = i[1]; int c = i[2]; int d = i[3]; row[a][b]++; row[b]--; col[a][d + 1]--; col[d + 1]++; } // Update row and col array for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { row[j][i] += row[j - 1][i]; col[j][i] += col[j - 1][i]; } } // Traverse and update matrix for (int i = 0; i < N; i++) { matrix[i][0] = row[i][0] + col[i][0]; } for (int i = 1; i <= N; i++) { for (int j = 0; j < N; j++) { matrix[j][i] += matrix[j][i - 1] + row[j][i] + col[j][i]; } } // resultant answer vector int res[][] = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) res[i][j] = matrix[i][j]; return res; } // function to print resultant matrix public static void printAns(int res[][]) { for (int i = 0; i < res.length; i++) { for (int j = 0; j < res[0].length; j++) { System.out.print(res[i][j] + " "); } System.out.println(); } } // Driver Code public static void main(String[] args) { int N = 6; int q = 6; int Queries[][] = { { 4, 0, 5, 3 }, { 0, 0, 3, 4 }, { 1, 2, 1, 2 }, { 1, 1, 2, 3 }, { 0, 0, 3, 1 }, { 1, 0, 2, 4 } }; int res[][] = solveQueries(N, Queries); printAns(res); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to solve q Queriesdef solveQueries(N, Queries): # // Initialize vectors matrix = [0]*(N+2) # (N + 2); for i in range(0, len(matrix)): matrix[i] = [0] * (N+2) row = [0]*(N+2) for i in range(0, len(row)): row[i] = [0]*(N+2) col = [0]*(N+2) for i in range(0, len(col)): col[i] = [0]*(N+2) # // Traverse over the queries for i in range(0, len(Queries)): a = Queries[i][0] b = Queries[i][1] c = Queries[i][2] d = Queries[i][3] row[a][b] += 1 row[b] -= 1 col[a][d + 1] -= 1 col[d + 1] += 1 for i in range(0, N): for j in range(1, N): row[j][i] += row[j - 1][i] col[j][i] += col[j - 1][i] # // Traverse and update matrix vector for i in range(0, N): matrix[i][0] = row[i][0] + col[i][0] for i in range(1, N+1): for j in range(0, N): matrix[j][i] += (matrix[j][i - 1]+row[j][i]+col[j][i]) res = [0]*(N) for i in range(0, len(res)): res[i] = [0]*N # new Array(N).fill(0); for i in range(0, N): for j in range(0, N): res[i][j] = matrix[i][j] return res# // function to prlet resultant matridef printAns(res): for i in range(0, len(res)): for j in range(0, len(res[0])): print(res[i][j],end=" ") print()# Driver CodeN = 6q = 6Queries = [[4, 0, 5, 3], [0, 0, 3, 4], [1, 2, 1, 2], [1, 1, 2, 3], [0, 0, 3, 1], [1, 0, 2, 4]]res = solveQueries(N, Queries)printAns(res)# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;class GFG { // Function to solve q Queries public static int[, ] solveQueries(int N, int[, ] Queries) { // Initialize arrays int[, ] matrix = new int[N + 2, N + 2]; int[, ] row = new int[N + 2, N + 2]; int[, ] col = new int[N + 2, N + 2]; // Traverse over the queries for (int i = 0; i < Queries.GetLength(0); i++) { int a = Queries[i, 0]; int b = Queries[i, 1]; int c = Queries[i, 2]; int d = Queries[i, 3]; row[a, b]++; row--; col[a, d + 1]--; col++; } // Update row and col array for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { row[j, i] += row[j - 1, i]; col[j, i] += col[j - 1, i]; } }РЕКОМЕНДУЕМЫЕ СТАТЬИ |