数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找矩阵中正方形的最大边长
在这个问题中，我们得到一个大小为 n 的二维矩阵 mat[][]，其中 n 是奇数。我们的任务是在矩阵中找到正方形的最大边长。
问题描述 - 我们需要找到一个方形矩阵的边长，其周长值相同，并且与矩阵共享相同的中心。
让我们举个例子来理解这个问题，
输入
mat[][] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
}输出
3
解决方案方法
解决该问题的一个简单方法是找到矩阵的中心元素，因为它是奇数矩阵，所以中心元素将在索引 (n/2, n/2) 处。找到中心后，我们将找到围绕它的所有二维子矩阵，这些子矩阵将检查其所有元素是否相同。
距离中心 i 索引处的子矩阵将具有从索引 (n/2 - 1) 到 (n/2 + 1) 的行 (n/2 - 1) 和 (n/2 + 1) 的元素。此外，其周长还包括从索引 (n/2 - 1) 到 (n/2 + 1) 的列 (n/2 - 1) 和 (n/2 + 1) 的元素。我们需要检查从 0 到 n/2 的任何 i 值的子矩阵的所有周长元素是否相同。
程序说明了我们解决方案的工作原理，
示例
#include <iostream>
#define n 5
using namespace std;
int findMaxSideSquare(int matrix[][n]) {
int squareLen = 1;
for (int i = 0; i < n / 2; i++) {
int sideVal = matrix[i][i];
bool isSquare = true;
for (int j = i; j < n - i; j++) {
if (matrix[i][j] != sideVal)
isSquare = false;
if (matrix[n - i - 1][j] != sideVal)
isSquare = false;
if (matrix[j][i] != sideVal)
isSquare = false;
if (matrix[j][n - i - 1] != sideVal)
isSquare = false;
}
if (isSquare)
squareLen = n - 2 * i;
}
return squareLen;
}
int main() {
int mat[n][n] = {
{2, 4, 6, 6, 5},
{1, 7, 7, 7, 3},
{5, 7, 0, 7, 1},
{3, 7, 7, 7, 1},
{2, 0, 1, 3, 2}
};
cout<<"The maximum side length of square in a Matrix is "<<findMaxSideSquare(mat);
return 0;
}输出
The maximum side length of square in a Matrix is 3
更新于: 2021年3月12日
213 次查看
广告