ในปัญหานี้ เราได้รับเมทริกซ์แบบ 2 มิติ[][] ขนาด n, 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
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือ การหาองค์ประกอบศูนย์กลางของ thematrix เนื่องจากเป็นเมทริกซ์คี่ องค์ประกอบศูนย์กลางจะอยู่ที่ดัชนี (n/2, n/2) หลังจากหาจุดศูนย์กลางแล้ว เราจะพบ 2D sub- เมทริกซ์ที่อยู่รอบๆ ซึ่งจะตรวจสอบว่าองค์ประกอบทั้งหมดเหมือนกันหรือไม่
เมทริกซ์ย่อยที่ดัชนี 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) ที่ปริมณฑล เราจำเป็นต้องตรวจสอบว่าเมทริกซ์ย่อยสำหรับค่าใด ๆ ของ i ตั้งแต่ 0 ถึง n/2 มีองค์ประกอบปริมณฑลเหมือนกันหรือไม่
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
