Untermatrix mit der gegebenen Summe finden
Bei einer gegebenen N x N -Matrix und zwei ganzen Zahlen S und K besteht die Aufgabe darin, herauszufinden, ob es eine K x K -Untermatrix mit einer Summe gleich S gibt .
Beispiele:
Eingabe: K = 2, S = 14, mat[][] = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 }}
Ausgabe: Ja
1 2
5 6
ist die erforderliche 2 x 2-Untermatrix mit Elementsumme = 14Eingabe: K = 1, S = 5, mat[][] = {{1, 2}, {7, 8}}
Ausgabe: Nr
Ansatz: Zur Lösung dieses Problems kann dynamische Programmierung eingesetzt werden,
- Erstellen Sie ein Array dp[N + 1][N + 1] wobei dp[i][j] die Summe aller Elemente mit Zeile zwischen 1 bis i und Spalte zwischen 1 bis j speichert .
- Sobald die 2-D-Matrix generiert ist, nehmen wir nun an, wir möchten die Summe der Quadrate beginnend mit (i, j) bis (i + x, j + x) ermitteln . Die erforderliche Summe ist dp[i + x][j + x] – dp[i][j + x] – dp[i + x][j] + dp[i][j] wobei,
- Der erste Term bezeichnet die Summe aller Elemente, die in Zeilen zwischen 1 bis i + x und Spalten zwischen 1 bis j + x vorhanden sind . Dieser Bereich hat unser erforderliches Quadrat.
- Die zweiten beiden Terme bestehen darin, den Bereich zu entfernen, der außerhalb unserer erforderlichen Region, aber innerhalb der im ersten Schritt berechneten Region liegt.
- Die Summe der Elemente der Zeilen zwischen 1 bis i und Spalten zwischen 1 bis j wird im zweiten Schritt zweimal subtrahiert, also einmal addiert.
Unten ist die Implementierung des obigen Ansatzes:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long int #define N 4 // Function to return the sum of the sub-matrix int getSum(int r1, int r2, int c1, int c2, int dp[N + 1][N + 1]) { return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1]; } // Function that returns true if it is possible // to find the sub-matrix with required sum bool sumFound(int K, int S, int grid[N][N]) { // 2-D array to store the sum of // all the sub-matrices int dp[N + 1][N + 1]; // Filling of dp[][] array for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + grid[i][j]; // Checking for each possible sub-matrix of size k X k for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { int sum = getSum(i, i + K, j, j + K, dp); if (sum == S) return true; } // Sub-matrix with the given sum not found return false; } // Driver code int main() { int grid[N][N] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int K = 2; int S = 14; // Function call if (sumFound(K, S, grid)) cout << "Yes" << endl; else cout << "No" << endl; } // Modified by Kartik Verma
Java
// Java implementation of the approach class GfG { static int N = 4; // Function to return the sum of the sub-matrix static int getSum(int r1, int r2, int c1, int c2, int dp[][]) { return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1]; } // Function that returns true if it is possible // to find the sub-matrix with required sum static boolean sumFound(int K, int S, int grid[][]) { // 2-D array to store the sum of // all the sub-matrices int dp[][] = new int[N + 1][N + 1]; // Filling of dp[][] array for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + grid[i][j]; } } // Checking for each possible sub-matrix of size k X // k for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int sum = getSum(i, i + K, j, j + K, dp); if (sum == S) { return true; } } } // Sub-matrix with the given sum not found return false; } // Driver code public static void main(String[] args) { int grid[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int K = 2; int S = 14; // Function call if (sumFound(K, S, grid)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code contributed by Rajput-Ji // Modified by Kartik Verma
Python3
# Python implementation of the approach N = 4 # Function to return the sum of the sub-matrix def getSum(r1, r2, c1, c2, dp): return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1] # Function that returns true if it is possible # to find the sub-matrix with required sum def sumFound(K, S, grid): # 2-D array to store the sum of # all the sub-matrices dp = [[0 for i in range(N+1)] for j in range(N+1)] # Filling of dp[][] array for i in range(N): for j in range(N): dp[i + 1][j + 1] = dp[i + 1][j] + \ dp[i][j + 1] - dp[i][j] + grid[i][j] # Checking for each possible sub-matrix of size k X k for i in range(0, N): for j in range(0, N): sum = getSum(i, i + K, j, j + K, dp) if (sum == S): return True # Sub-matrix with the given sum not found return False # Driver code grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] K = 2 S = 14 # Function call if (sumFound(K, S, grid)): print("Yes") else: print("No") # This code is contributed by ankush_953 # Modified by Kartik Verma
C#
// C# implementation of the approach using System; class GfG { static int N = 4; // Function to return the sum of the sub-matrix static int getSum(int r1, int r2, int c1, int c2, int[, ] dp) { return dp[r2, c2] - dp[r2, c1] - dp[r1, c2] + dp[r1, c1]; } // Function that returns true if it is possible // to find the sub-matrix with required sum static bool sumFound(int K, int S, int[, ] grid) { // 2-D array to store the sum of // all the sub-matrices int[, ] dp = new int[N + 1, N + 1]; // Filling of dp[,] array for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i + 1, j + 1] = dp[i + 1, j] + dp[i, j + 1] - dp[i, j] + grid[i, j]; } } // Checking for each possible sub-matrix of size k X // k for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int sum = getSum(i, i + K, j, j + K, dp); if (sum == S) { return true; } } } // Sub-matrix with the given sum not found return false; } // Driver code public static void Main(String[] args) { int[, ] grid = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int K = 2; int S = 14; // Function call if (sumFound(K, S, grid)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code has been contributed by 29AjayKumar // Modified by Kartik Verma
PHP
<?php // PHP implementation of the approach $GLOBALS['N'] = 4; // Function to return the sum of // the sub-matrix function getSum($r1, $r2, $c1, $c2, $dp) { return $dp[$r2][$c2] - $dp[$r2][$c1] - $dp[$r1][$c2] + $dp[$r1][$c1]; } // Function that returns true if it is // possible to find the sub-matrix with // required sum function sumFound($K, $S, $grid) { // 2-D array to store the sum of // all the sub-matrices $dp = array(array()); for ($i = 0; $i < $GLOBALS['N']; $i++) for ($j = 0; $j < $GLOBALS['N']; $j++) $dp[$i][$j] = 0 ; // Filling of dp[][] array for ($i = 0; $i < $GLOBALS['N']; $i++) for ($j = 0; $j < $GLOBALS['N']; $j++) $dp[$i + 1][$j + 1] = $dp[$i + 1][$j] + $dp[$i][$j + 1] - $dp[$i][$j] + $grid[$i][$j]; // Checking for each possible sub-matrix // of size k X k for ($i = 0; $i < $GLOBALS['N']; $i++) for ($j = 0; $j < $GLOBALS['N']; $j++) { $sum = getSum($i, $i + $K, $j, $j + $K, $dp); if ($sum == $S) return true; } // Sub-matrix with the given // sum not found return false; } // Driver code $grid = array(array(1, 2, 3, 4), array(5, 6, 7, 8), array(9, 10, 11, 12), array(13, 14, 15, 16)); $K = 2; $S = 14; // Function call if (sumFound($K, $S, $grid)) echo "Yes"; else echo "No"; // This code is contributed by Ryuga //Modified by Kartik Verma ?>
Javascript
<script> // Javascript implementation of the approach var N = 4 // Function to return the sum of the sub-matrix function getSum(r1, r2, c1, c2, dp) { return dp[r2][c2] - dp[r2][c1] - dp[r1][c2] + dp[r1][c1]; } // Function that returns true if it is possible // to find the sub-matrix with required sum function sumFound(K, S, grid) { // 2-D array to store the sum of // all the sub-matrices var dp = Array.from(Array(N+1), ()=> Array(N+1).fill(0)); // Filling of dp[][] array for (var i = 0; i < N; i++) for (var j = 0; j < N; j++) dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + grid[i][j]; // Checking for each possible sub-matrix of size k X k for (var i = 0; i < N; i++) for (var j = 0; j < N; j++) { var sum = getSum(i, i + K, j, j + K, dp); if (sum == S) return true; } // Sub-matrix with the given sum not found return false; } // Driver code var grid = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ]; var K = 2; var S = 14; // Function call if (sumFound(K, S, grid)) document.write( "Yes"); else document.write( "No" ); </script>
Ausgabe:
ja
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .