Chúng ta được cho một ma trận các số. Mục tiêu là tìm số Magic Square có mặt bên trong ma trận đã cho.
Một Magic Square, nếu lấy như một ma trận, là ma trận 3x3 chứa các phần tử từ 1 đến 9 giống như lưới trong Sudoku. Các tính chất:
- Tất cả số xuất hiện đúng một lần.
- Tổng 9 ô trong ma trận là 45.
- Tổng mỗi hàng 3 ô là 15.
- Tổng mỗi cột 3 ô là 15.
- Tổng đường chéo 3 ô là 15.
- Để có các tổng như vậy, 5 luôn ở giữa của cả hai đường chéo.
Ví dụ
Đầu vào
int arr[][] = { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };
Đầu ra
Magic Square có mặt: 0
Giải thích − Tạo dạng ma trận để hiểu:
| 1 | 2 | 3 | 0 |
| 4 | 5 | 6 | 1 |
| 7 | 8 | 9 | 0 |
Tất cả phần tử từ 1 đến 9 và duy nhất. Nhưng:
1+2+3=6 != 4+5+6=15 != 7+8+9=23
Cũng tổng đường chéo không bằng 15.
Đầu vào
arr[][] = { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };
Đầu ra
Magic Square có mặt: 1
Giải thích − Dạng ma trận:
| 1 | 6 | 8 | 4 |
| 8 | 1 | 6 | 0 |
| 3 | 5 | 7 | 1 |
| 4 | 9 | 2 | 0 |
Tất cả số duy nhất và trong khoảng 1 đến 9.
Tổng hàng: 8+1+6=3+5+7=4+9+2=15
Tổng cột: 8+3+4=1+5+9=6+7+2=15
Tổng đường chéo: 8+5+2=4+5+6=15
Cũng cộng 1 đến 9 được 45, và 5 ở giữa cả hai đường chéo.
Phương pháp sử dụng trong chương trình dưới đây
- Mảng số nguyên Grid[][] lưu số, row và col lưu kích thước.
- Hàm magicSquare(int a, int b... int i) nhận 9 phần tử làm đầu vào và kiểm tra nó có tạo thành magic square không. Trả về 1 nếu là magic square, trả về 0 ngược lại.
- Ở đây lấy mảng arr[9] lưu tất cả tham số và kiểm tra nếu chúng duy nhất bằng cách kiểm tra chúng chiếm ô duy nhất trong nó. Nếu ô có count < 1 nghĩa là số không trong khoảng 1-9, hoặc count > 1 thì số không duy nhất. Đặt flag = 0.
- Nếu flag là 1 thì kiểm tra tổng hàng, cột, đường chéo bằng 15. Nếu đúng thì là magic square. Trả về 1 ngược lại trả về 0.
- Hàm countSquares(int G[3][4], int R, int C) nhận lưới, hàng, cột và đếm số magic square có trong nó.
- Count lưu số lượng các square như vậy.
- Duyệt từ phần tử đầu tiên đến row-2, col-2 (ma trận 3x3).
- Nếu giữa đường chéo G[i+1][j+1] không phải 5 thì magic square không thể, bỏ qua vòng lặp hiện tại.
- Ngược lại kiểm tra 9 phần tử bằng cách truyền cho magicSquare(int a đến i).
- Tất cả 9 phần tử bao gồm G[i][j] là G[i+1][j], G[i+2][j], G[i+1][j+1], G[i][j+1], G[i][j+2], G[i+2][j+2], G[i+2][j+1], G[i+1][j+2].
- Nếu trả về 1 thì tăng count.
- Cuối cùng trả về count là kết quả mong muốn.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra subgrid có phải Magic Square
int magicSquare(int a, int b, int c, int d, int e, int f, int g, int h, int i) {
int flag = 1; // đánh dấu tất cả số duy nhất và 1-9
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 i = 0; i < 9; i++)
if (arr[i] > 1 || arr[i] < 1) { // mỗi số xuất hiện đúng một lần
flag = 0;
break;
}
// Kiểm tra tất cả tổng bằng 15
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]);
// kiểm tra magic square subgrid
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;
int col = 4;
cout << "Số Magic Square trong Grid: " << countSquares(Grid, row, col);
return 0;
}
Kết quả
Số Magic Square trong Grid: 1