Hướng dẫn giải của Ma trận xoắn ốc 1
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for ptit006: Ma trận xoắn ốc 1
Hiểu bài toán
Xây dựng ma trận xoắn ốc (spiral matrix) kích thước n x n, điền các số từ 1 đến n*n theo thứ tự xoắn ốc từ ngoài vào trong, bắt đầu từ ô (0,0) và đi theo chiều kim đồng hồ (trên -> phải -> dưới -> trái). Ví dụ: n=3 cho ma trận: 1 2 3 8 9 4 7 6 5
Các cách tiếp cận
Cách Simulation (Boundary Tracking)
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[51][51];
int top = 0, bottom = n - 1, left = 0, right = n - 1;
int val = 1;
while (val <= n * n) {
// Left to right
for (int i = left; i <= right; i++) {
a[top][i] = val++;
}
top++;
// Top to bottom
for (int i = top; i <= bottom; i++) {
a[i][right] = val++;
}
right--;
// Right to left
for (int i = right; i >= left; i--) {
a[bottom][i] = val++;
}
bottom--;
// Bottom to top
for (int i = bottom; i >= top; i--) {
a[i][left] = val++;
}
left++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(n²)
- Space Complexity: O(n²)
Phương pháp mô phỏng trực tiếp quá trình điền ma trận. Dùng 4 biến để lưu границы: top, bottom, left, right. Vòng lặp while thực hiện 4 bước: đi phải (top), đi xuống (right), đi trái (bottom), đi lên (left). Sau mỗi bước, thu hẹp biên tương ứng. Điều kiện dừng khi đã điền đủ n*n số. Phương pháp này mô phỏng đúng cơ chế hình thành xoắn ốc.
Cách Mathematical Formula (Layer Calculation)
#include <stdio.h>
int min(int a, int b) { return a < b ? a : b; }
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int layer = min(min(i, j), min(n - 1 - i, n - 1 - j));
int side = n - 2 * layer;
int start = (layer == 0) ? 0 : 4 * (n - 1) * layer - 4 * layer * (layer - 1);
int offset;
if (i == layer) offset = j - layer; // Top edge
else if (j == n - 1 - layer) offset = (side - 1) + (i - layer); // Right edge
else if (i == n - 1 - layer) offset = 2 * (side - 1) + (n - 1 - layer - j); // Bottom edge
else offset = 3 * (side - 1) + (n - 1 - layer - i); // Left edge
printf("%d ", start + offset + 1);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(n²)
- Space Complexity: O(1)
Tính toán trực tiếp giá trị của mỗi ô dựa trên công thức toán học. Xác định 'layer' (lớp) của ô bằng khoảng cách gần nhất đến biên. Tính giá trị bắt đầu của layer đó, sau đó tính offset dựa trên vị trí tương đối của ô trong layer (trên, phải, dưới, trái). Phương pháp này không cần lưu ma trận, chỉ cần tính toán toán học.
Cách Direct Filling (Iterative)
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[50][50];
int h1 = 0, h2 = n - 1, c1 = 0, c2 = n - 1;
int dem = 1;
while (dem <= n * n) {
for (int i = c1; i <= c2; i++) a[h1][i] = dem++;
h1++;
for (int i = h1; i <= h2; i++) a[i][c2] = dem++;
c2--;
for (int i = c2; i >= c1; i--) a[h2][i] = dem++;
h2--;
for (int i = h2; i >= h1; i--) a[i][c1] = dem++;
c1++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
- Time Complexity: O(n²)
- Space Complexity: O(n²)
Đây là biến thể của phương pháp mô phỏng, sử dụng biến đếm để kiểm soát vòng lặp thay vì điều kiện biên. Logic tương tự: điền 4 cạnh của mỗi lớp xoắn ốc và thu hẹp biên. Điều kiện dừng là khi biến đếm vượt quá n*n. Đây là cách tiếp cận trực quan và dễ hiểu nhất.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n²) | O(n²) | Simulation (Boundary Tracking) |
| 2 | O(n²) | O(1) | Mathematical Formula (Layer Calculation) |
| 3 | O(n²) | O(n²) | Direct Filling (Iterative) |
Bài học kinh nghiệm
- Cần theo dõi 4 biên (trên, dưới, trái, phải) để biết đâu là ranh giới của lớp xoắn ốc hiện tại.
- Thứ tự điền luôn là: trái sang phải (trên), trên xuống dưới (phải), phải sang trái (dưới), dưới lên trên (trái).
- Sau mỗi 'vòng' xoắn ốc (4 cạnh), cần thu hẹp 4 biên vào trong.
Lỗi thường gặp
- Quên cập nhật biên sau khi điền một cạnh, dẫn đến ghi đè hoặc truy cập ngoài vùng nhớ.
- Xử lý sai trường hợp n lẻ (ô giữa cùng) hoặc n chẵn.
- Lỗi off-by-one: điều kiện dừng vòng lặp (<= hay <) sai làm thiếu hoặc thừa số.
- Điều kiện while có thể gây truy cập ma trận rỗng nếu biên bị ngược (top > bottom hoặc left > right).
Bình luận