หาความยาวด้านสูงสุดของสี่เหลี่ยมจัตุรัสในเมทริกซ์ใน C++

คำอธิบายปัญหา

ได้รับเมทริกซ์ 2D ขนาด n x n (โดย n เป็นเลขคี่) ต้องการหา ความยาวด้านสูงสุดของสี่เหลี่ยมจัตุรัส ที่:

1. มีศูนย์กลางตรงกับศูนย์กลางของเมทริกซ์
2. ค่าบน เส้นรอบรูป (Perimeter) ของสี่เหลี่ยมจัตุรัสมีค่า เท่ากันทุกตัว

ตัวอย่าง

Input:
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}
}

Output: 3

คำอธิบาย: สี่เหลี่ยมจัตุรัสขนาด 3x3 ตรงกลาง มีเส้นรอบรูปเป็น 7 ทั้งหมด (index 1 ถึง 3 ทั้งแถวและคอลัมน์)

แนวทางแก้ปัญหา

1. หา ศูนย์กลาง ของเมทริกซ์: center = n/2 (0-indexed)
2. ตรวจสอบสี่เหลี่ยมจัตุรัสแต่ละขนาด โดยขยายออกจากศูนย์กลางทีละชั้น (i = 0 ถึง n/2):
   • สี่เหลี่ยมที่ห่างจากศูนย์กลาง i ชั้น จะมีขนาด n - 2*i
   • ตรวจสอบเส้นรอบรูป 4 ด้าน: แถวบน, แถวล่าง, คอลัมน์ซ้าย, คอลัมน์ขวา
   • ถ้าค่าทุกตัวบนเส้นรอบรูปเท่ากัน → บันทึกความยาวด้าน
3. คืนค่าความยาวด้านสูงสุดที่พบ

โค้ดตัวอย่าง C++

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

int findMaxSideSquare(int matrix[][n]) {
    int squareLen = 1;  // ขนาด 1x1 เสมอเป็นจริง (แค่จุดกึ่งกลาง)
    
    for (int i = 0; i < n / 2; i++) {
        int sideVal = matrix[i][i];  // ค่าที่คาดหวังบนเส้นรอบรูป
        bool isSquare = true;
        
        for (int j = i; j < n - i; j++) {
            // ตรวจสอบ 4 ด้าน
            if (matrix[i][j] != sideVal) isSquare = false;           // Top
            if (matrix[n - i - 1][j] != sideVal) isSquare = false;   // Bottom
            if (matrix[j][i] != sideVal) isSquare = false;           // Left
            if (matrix[j][n - i - 1] != sideVal) isSquare = false;   // Right
        }
        
        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