在矩陣中打印具有相同矩形和的單元格 · GeeksForGeeks 中文系列教程

# 在矩陣中打印具有相同矩形和的單元格 > 原文： [https://www.geeksforgeeks.org/print-cells-rectangular-sum-matrix/](https://www.geeksforgeeks.org/print-cells-rectangular-sum-matrix/) 給定一個 m x n 矩陣的矩陣，我們需要打印所有子矩陣，這些子矩陣的總和在此單元結束，并且子矩陣從該單元開始等于其余元素。為了更好地理解，請參見下圖， **示例**： ``` 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 <font color="Red">red</font> area is equal to <font color="Green">green</font> area. ``` 首先，我們[構造類似于鏈接文章的輔助子矩陣](https://www.geeksforgeeks.org/submatrix-sum-queries/)。我們構造兩個矩陣 sum [] []和 sumr [] []，使得 **sum [i] [j]** 表示從 mat [0] [0]到 mat [i] [ j]。用于存儲總和直到最后一個索引的求和器，即 **sumr [i] [j]** 表示子矩陣 mat [i] [j]與 mat [m – 1] [n – 1]的總和。現在我們可以使用上述矩陣來解決此問題，可以通過將求和矩陣與求和矩陣相加相應的像元來計算上圖中的紅色區域，因為在計算此和時要考慮兩次 mat [i] [j] 減去一次即可得到紅色區域的總和。獲取剩余元素的總和（綠色部分）非常容易，我們將從給定矩陣的總和中減去紅色部分的總和。因此，要檢查特定單元格是否滿足給定條件，我們將如上所述計算紅色部分的總和，并將其與矩陣的總和進行比較，如果該總和為矩陣總和的一半，則當前單元格滿足條件，因此結果的候選人。 ## C/C++ ``` // C++ program to print cells with same rectangular // sum diagonally #include <bits/stdc++.h> using namespace std; #define R 4 #define C 4 // Method prints cell index at which rectangular sum is // same at prime diagonal and other diagonal void printCellWithSameRectangularArea(int mat[R][C], ?????????????????????????????????????int m, int n) { ????/* sum[i][j] denotes sum of sub-matrix, mat[0][0] ???????to mat[i][j] ???????sumr[i][j] denotes sum of sub-matrix, mat[i][j] ???????to mat[m - 1][n - 1]? */ ????int sum[m][n], sumr[m][n]; ????//? Initialize both sum matrices by 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]; ????????} ????} ????//? updating first and last row separately ????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]; ????} ????//? updating first and last column separately ????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]; ????} ????//? updating sum and sumr indices by nearby indices ????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]; ????????} ????} ????//? Uncomment below code to print sum and reverse sum ????// matrix ????/* ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????cout << sum[i][j] << " "; ????????????} ????????????cout << endl; ????????} ????????cout << endl; ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????cout << sumr[i][j] << " "; ????????????} ????????????cout << endl; ????????} ????????cout << endl;??? */ ????/* print all those indices at which sum of prime diagonal ???????rectangles is half of the total sum of matrix? */ ????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; ????????} ????} } //? Driver code to test above methods 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 ```java // Java program to print cells with? // same rectangular sum diagonally class GFG { static final int R = 4; static final int C = 4; // Method prints cell index at which? // rectangular sum is same at? // prime diagonal and other diagonal static void printCellWithSameRectangularArea(int mat[][],? ?????????????????????????????????????????????int m, int n)? { ????/* sum[i][j] denotes sum of sub-matrix, mat[0][0] ????to mat[i][j] ????sumr[i][j] denotes sum of sub-matrix, mat[i][j] ????to mat[m - 1][n - 1] */ ????int sum[][] = new int[m][n]; ????int sumr[][] = new int[m][n]; ????// Initialize both sum matrices by 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]; ????} ????} ????// updating first and last row separately ????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]; ????} ????// updating first and last column separately ????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]; ????} ????// updating sum and sumr indices by nearby indices ????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]; ????} ????} ????// Uncomment below code to print sum and reverse sum ????// matrix ????/* ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????System.out.print( sum[i][j] + " "); ????????????} ????????????System.out.println(); ????????} ????????System.out.println(); ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????System.out.print(sumr[i][j] + " "); ????????????} ????????????System.out.println(); ????????} ????????System.out.println(); */ ????/* print all those indices at which sum of prime diagonal ????rectangles is half of the total sum of matrix */ ????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 + ")"); ????} ????} } // Driver code 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); } } // This code is contributed by Anant Agarwal. ``` ## Python ``` # Python program to print cells with same rectangular # sum diagonally # R 4 # C 4 # Method prints cell index at which rectangular sum is # same at prime diagonal and other diagonal def printCellWithSameRectangularArea(mat, m, n): ????# sum[i][j] denotes sum of sub-matrix, mat[0][0] ????#? to mat[i][j] ????# sumr[i][j] denotes sum of sub-matrix, mat[i][j] ????# to mat[m - 1][n - 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)] ????#? Initialize both sum matrices by mat ????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] ????#? updating first and last row separately ????for i in range(1,m): ????????sum[i][0] += sum[i-1][0] ????????sumr[m-i-1][n-1] += sumr[m-i][n-1] ????#? updating first and last column separately ????for j in range(1,n): ????????sum[0][j] += sum[0][j-1]; ????????sumr[m-1][n-j-1] += sumr[m-1][n-j] ????#? updating sum and sumr indices by nearby indices ????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] ????#? Uncomment below code to print sum and reverse sum ????# matrix ????# print all those indices at which sum of prime diagonal ????#?? rectangles is half of the total sum of matrix?? ????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 ")", #? Driver code to test above methods mat =[[1, 2, 3, 5,], ?????[4, 1, 0, 2,], ?????[0, 1, 2, 0], ?????[7, 1, 1, 0]] printCellWithSameRectangularArea(mat, 4, 4) # Contributed by Afzal ``` ## C# ```cs // C# program to print cells with? // same rectangular sum diagonally using System; class GFG { static int R = 4; static int C = 4; // Method prints cell index at which? // rectangular sum is same at? // prime diagonal and other diagonal static void printCellWithSameRectangularArea(int [,]mat,? ?????????????????????????????????????????????int m, int n)? { ????/* sum[i][j] denotes sum of sub- ???????matrix, mat[0][0] to mat[i][j] ???????sumr[i][j] denotes sum of sub-matrix, ???????mat[i][j] to mat[m - 1][n - 1] */ ????int [,]sum = new int[m, n]; ????int [,]sumr = new int[m, n]; ????// Initialize both sum matrices by 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]; ????} ????} ????// updating first and last row separately ????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]; ????} ????// updating first and last column separately ????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]; ????} ????// updating sum and sumr indices by nearby indices ????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]; ????} ????} ????// Uncomment below code to print sum and reverse sum ????// matrix ????/* ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????System.out.print( sum[i][j] + " "); ????????????} ????????????System.out.println(); ????????} ????????System.out.println(); ????????for (int i = 0; i < m; i++) ????????{ ????????????for (int j = 0; j < n; j++) ????????????{ ????????????????System.out.print(sumr[i][j] + " "); ????????????} ????????????System.out.println(); ????????} ????????System.out.println(); */ ????/* print all those indices at which sum ???????of prime diagonal rectangles is half? ???????of the total sum of matrix */ ????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 + ")"); ????} ????} } // Driver code 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); } } // This code is contributed by vt_m. ``` Output: ``` (1, 1) (2, 2) ``` 本文由 [**Utkarsh Trivedi**](https://in.linkedin.com/in/utkarsh-trivedi-253069a7) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。