Trong bài toán này, chúng ta được đưa ra một ma trận 2-D [] [] có kích thước n, n là một số lẻ. Nhiệm vụ của chúng ta là Tìm độ dài cạnh tối đa của một hình vuông trong Ma trận.
Mô tả sự cố - Chúng ta cần tìm độ dài của ma trận vuông có các giá trị chu vi bằng nhau và nó có cùng tâm với ma trận.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
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}
} Đầu ra
3
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm phần tử trung tâm của thematrix vì nó là một ma trận lẻ, phần tử trung tâm sẽ ở chỉ số (n / 2, n / 2). ma trận xung quanh nó sẽ kiểm tra xem tất cả các phần tử của nó có giống nhau không.
Ma trận con tại chỉ số i cách xa tâm sẽ có một phần tử của hàng (n / 2 - 1) và (n / 2 + 1) từ chỉ số (n / 2 - 1) đến (n / 2 + 1). Ngoài ra, các phần tử của cột (n / 2 - 1) và (n / 2 + 1) từ chỉ số (n / 2 - 1) đến (n / 2 + 1) cũng được bao gồm trong chu vi của nó. Chúng ta cần kiểm tra xem ma trận con với bất kỳ giá trị nào của i từ 0 đến n / 2 có tất cả các phần tử chu vi giống nhau hay không.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The maximum side length of square in a Matrix is 3