資料結構
網路
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 次檢視
廣告