เราได้รับเมทริกซ์ตัวเลข เป้าหมายคือหาจำนวน Magic Squares ภายในเมทริกซ์นั้น
Magic Square (ถ้ามองเป็นเมทริกซ์) คือเมทริกซ์ 3x3 ที่มีตัวเลข 1 ถึง 9 ครั้งละ 1 ครั้ง (เหมือนกริดซูโดกุ) คุณสมบัติ:
- ตัวเลขทุกตัวเกิดขึ้นครั้งละ 1 ครั้ง
- ผลรวมทั้ง 9 เซลล์ = 45
- ผลรวมแต่ละแถว 3 ตัว = 15
- ผลรวมแต่ละคอลัมน์ 3 ตัว = 15
- ผลรวมเส้นทแยงมุม 3 ตัว = 15
- เพื่อให้ได้ผลรวมเหล่านี้ 5 ต้องอยู่ตรงกลางเส้นทแยงมุมทั้งสองเสมอ
อินพุต
int arr[][] = {{1,2,3,0}, {4,5,6,1}, {7,8,9,0}};
เอาต์พุต
Magic Squares present: 0
คำอธิบาย − ตัวเลข 1-9 ครบและไม่ซ้ำ แต่ผลรวมแถว: 1+2+3=6 ≠ 4+5+6=15 ≠ 7+8+9=24 เส้นทแยงมุมก็ไม่ได้ 15
อินพุต
arr[][] = {{8,1,6,4}, {3,5,7,0}, {4,9,2,0}};
เอาต์พุต
Magic Squares present: 1
คำอธิบาย − ตัวเลข 1-9 ครบไม่ซ้ำ ผลรวมแถว: 8+1+6=3+5+7=4+9+2=15 คอลัมน์: 8+3+4=1+5+9=6+7+2=15 เส้นทแยง: 8+5+2=4+5+6=15 รวม 1-9 = 45 และ 5 อยู่กลาง
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ Grid[][] เก็บตัวเลข row, col เก็บมิติ
- ฟังก์ชัน magicSquare(int a...int i) รับ 9 ตัวเลข ตรวจสอบว่าเป็น Magic Square คืน 1 ถ้าใช่ มิฉะนั้น 0
- ใช้ arr[9] เก็บตัวเลข ตรวจสอบความครบและไม่ซ้ำ (count ต้องเป็น 1 ทุกตัว) มิฉะนั้น flag=0
- ถ้า flag=1 ตรวจสอบผลรวมแถว, คอลัมน์, เส้นทแยง = 15 คืน 1 มิฉะนั้น 0
- ฟังก์ชัน countSquares(int G[3][4], int R, int C) นับ Magic Squares ในกริด
- ลูป i=0 ถึง R-2, j=0 ถึง C-2 (เมทริกซ์ 3x3)
- ถ้ากลางเส้นทแยง G[i+1][j+1] != 5 ข้าม (ไม่เป็น Magic Square)
- ส่ง 9 ตัวเลขเข้า magicSquare() ถ้าคืน 1 เพิ่ม count
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int magicSquare(int a, int b, int c, int d, int e, int f, int g, int h, int i) {
int flag = 1;
int arr[9] = {0};
arr[a-1]++; arr[b-1]++; arr[c-1]++; arr[d-1]++; arr[e-1]++;
arr[f-1]++; arr[g-1]++; arr[h-1]++; arr[i-1]++;
for (int k = 0; k < 9; k++)
if (arr[k] > 1 || arr[k] < 1) { flag = 0; break; }
if (flag == 1 && (a+b+c)==15 && (d+e+f)==15 && (g+h+i)==15 &&
(a+d+g)==15 && (b+e+h)==15 && (c+f+i)==15 &&
(a+e+i)==15 && (c+e+g)==15)
return 1;
return 0;
}
int countSquares(int G[3][4], int R, int C) {
int count = 0;
for (int i = 0; i < R - 2; i++)
for (int j = 0; j < C - 2; j++) {
if (G[i+1][j+1] != 5) continue;
int ismagic = magicSquare(G[i][j], G[i][j+1], G[i][j+2],
G[i+1][j], G[i+1][j+1], G[i+1][j+2],
G[i+2][j], G[i+2][j+1], G[i+2][j+2]);
if (ismagic == 1) count++;
}
return count;
}
int main() {
int Grid[3][4] = {{4,3,8,4}, {9,5,1,9}, {2,7,6,2}};
int row = 3, col = 4;
cout << "Count of Magic Squares in Grid: " << countSquares(Grid, row, col);
return 0;
}
ผลลัพธ์
Count of Magic Squares in Grid: 1
