数据结构
网络
关系数据库管理系统 (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 次浏览
