Tìm độ dài cạnh lớn nhất của hình vuông trong ma trận C++

Mô tả vấn đề

Cho ma trận vuông mat[][] kích thước n (số lẻ). Tìm độ dài cạnh lớn nhất của hình vuông đồng tâm (cùng tâm với ma trận) có tất cả các phần tử trên chu vi bằng nhau.

Ví dụ minh họa

Đầ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 giải quyết

Tâm ma trận lẻ tại (n/2, n/2). Kiểm tra các hình vuông đồng tâm với bán kính i từ 0 đến n/2. Hình vuông bán kính i có chu vi gồm:

• Hàng n/2 - i và n/2 + i từ cột n/2 - i đến n/2 + i
• Cột n/2 - i và n/2 + i từ hàng n/2 - i đến n/2 + i

Chương trình minh họa

#include <iostream>
#define n 5
using namespace std;

int findMaxSideSquare(int matrix[][n]) {
    int squareLen = 1; // Tối thiểu là 1 (chỉ tâm)
    for (int i = 0; i < n / 2; i++) {
        int sideVal = matrix[i][i]; // Giá trị góc trên-trái của vuông hiện tạ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 << "Độ dài cạnh lớn nhất của hình vuông trong ma trận là " << findMaxSideSquare(mat);
    return 0;
}

Kết quả đầu ra

Độ dài cạnh lớn nhất của hình vuông trong ma trận là 3