資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學用 C++ 列印矩陣中具有相同矩形和的單元格
在這個問題中，我們得到一個大小為 mXn 的整數矩陣 *mat*。我們的任務是建立一個程式來 *列印矩陣中具有相同矩形和的單元格*。
問題描述：我們將找到矩陣中的一個單元格，其方式是**以該單元格為起點和終點的子矩陣的和等於所有剩餘元素的和**。
對於一個單元格，矩陣 (a, b) 子矩陣 mat[0][0] 到 mat[a][b] 和 mat[a][b] 到 mat[m][n] 的和等於所有剩餘元素的和。
讓我們來看一個例子來理解這個問題：
輸入：mat[][] = { {5, 0, 2, 7}
{3, 0, 1, 0}
{1, 4, 1, 3}
{10, 0, 2, 1}}
輸出：(2, 1)
解釋：
對於元素 (2,3)
子矩陣1 為 - { {5, 0}
{3, 0}
{1, 4}}
子矩陣2 為 - { {4, 1, 3}
{0, 2, 1}}
總和 = 5 + 0 + 3 + 0 + 1 + 4 + 1 + 3 + 0 + 2 + 1 = 20
其餘元素的總和 = 2 + 7 + 1 + 0 + 10 = 20
解決方案
為了解決這個問題，我們需要建立兩個輔助子矩陣，aux1[m][n] 和 aux2[m][n]。aux1[i][j] 將儲存從 (0,0) 到 (i, j) 的所有元素的和，而 aux2[i][j] 將儲存從 (i,j) 到 (n, m) 的所有元素的和。然後我們將兩個和相加，並減去 mat(i,j)，因為它將出現兩次。
然後我們將這個和與矩陣所有元素的和進行比較。如果單元格中的和是矩陣和的一半，那麼該單元格就是結果，我們將列印它。
程式說明了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
#define R 4
#define C 4
void findCellWithSameRectSum(int mat[R][C]) {
int m = R, n = C;
int aux1[m][n], aux2[m][n];
int matSum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux2[i][j] = aux1[i][j] = mat[i][j];
matSum += mat[i][j];
}
}
for (int i = 1; i < m; i++) {
aux1[i][0] += aux1[i-1][0];
aux2[m-i-1][n-1] += aux2[m-i][n-1];
}
for (int j = 1; j < n; j++) {
aux1[0][j] += aux1[0][j-1];
aux2[m-1][n-j-1] += aux2[m-1][n-j];
}
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) {
aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
cout << "(" << i << ", " << j << ")\t";
}
int main() {
int mat[R][C] = {{5, 0, 2, 7},
{3, 0, 1, 0},
{1, 4, 1, 3},
{10, 0, 2, 1}};
cout<<"The cells with same rectangular sums in a matrix is \n";
findCellWithSameRectSum(mat);
return 0;
}輸出
The cells with same rectangular sums in a matrix is (1, 1) (2, 1)
85 次瀏覽
