Editorial for rsprial: Ma trận xoắn ốc 2

Hiểu bài toán

Bài toán yêu cầu duyệt và in ra các phần tử của một ma trận kích thước m x n theo thứ tự xoắn ốc, bắt đầu từ góc trên bên trái và di chuyển theo chiều kim đồng hồ vào tâm. Input gồm m, n và ma trận, output là các phần tử theo thứ tự xoắn ốc, cách nhau bởi dấu cách. Ma trận có thể có một hàng hoặc một cột.

Các cách tiếp cận

Cách Simulation with Boundary Tracking

#include <stdio.h>

int a[1001][1001];

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int top = 0, bottom = m - 1;
    int left = 0, right = n - 1;
    int count = 0;
    int total = m * n;
    while (count < total) {
        // Left to right
        for (int i = left; i <= right && count < total; i++) {
            printf("%d ", a[top][i]);
            count++;
        }
        top++;
        // Top to bottom
        for (int i = top; i <= bottom && count < total; i++) {
            printf("%d ", a[i][right]);
            count++;
        }
        right--;
        // Right to left
        for (int i = right; i >= left && count < total; i--) {
            printf("%d ", a[bottom][i]);
            count++;
        }
        bottom--;
        // Bottom to top
        for (int i = bottom; i >= top && count < total; i--) {
            printf("%d ", a[i][left]);
            count++;
        }
        left++;
    }
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Phương pháp này sử dụng 4 biến để mô phỏng các đường biên của ma trận hiện tại: 'top', 'bottom', 'left', 'right'. Ta thực hiện 4 vòng lặp tương ứng với 4 hướng (trái sang phải, trên xuống dưới, phải sang trái, dưới lên trên) để duyệt các phần tử ở mép ngoài cùng của ma trận. Sau khi duyệt xong một vòng, ta thu hẹp các biên lại (top++, bottom--, left++, right--) và lặp lại cho đến khi tất cả các phần tử都被in ra. Điều kiện dừng 'count < total' đảm bảo không in thừa phần tử khi ma trận có một hàng hoặc một cột.

Cách Direct Simulation (Submission 1)

#include<stdio.h>
#include<math.h>
 int a[1001][1001];
int main()
{
   int m,n,i,j;
   scanf("%d%d",&m,&n);
   for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
     scanf("%d",&a[i][j]);
   int trai,phai,tren,duoi;
   trai=1;phai=n;tren=1;duoi=m;
   int d=1;
   while(d<=m*n)
   {
    for(i=trai;i<=phai;i++)
        printf("%d ",a[tren][i]);
     tren++;
    for(i=tren;i<=duoi;i++)
        printf("%d ",a[i][phai]);
     phai--;
    for(i=phai;i>=trai;i--)
        printf("%d ",a[duoi][i]);
    duoi--;
    for(i=duoi;i>=tren;i--)
        printf("%d ",a[i][trai]);
    trai++;
    d++;
   }
     return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Đây là một cách cài đặt trực tiếp của phương pháp boundary tracking, sử dụng 1-based indexing. Tuy nhiên, nó có một sai sót logic: biến 'd' được tăng sau mỗi vòng lặp while (kể cả khi chỉ in một phần tử), và không có kiểm tra điều kiện dừng bên trong các vòng lặp for. Điều này có thể dẫn đến in thừa các phần tử hoặc lỗi với các ma trận không vuông/vuông không đúng kích thước (ví dụ ma trận 1 hàng). Ví dụ, với ma trận 1xN, vòng lặp đầu tiên sẽ in hết hàng, sau đó 'tren' tăng lên 2, vòng lặp thứ hai sẽ cố gắng in cột phải từ hàng 2 đến hàng 1 (không in gì), vòng lặp thứ ba sẽ cố in hàng dưới từ phải sang trái, nhưng 'duoi' vẫn là 'm' (ví dụ 1), và 'trai' là 1, 'phai' là N-1, nó sẽ in từ N-1 về 1, gây ra in sai.

Cách Corrected Simulation with Early Exit (Submission 3)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define ll long long
#define modulo 1000000007

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &a[i][j]);
        }
    }
    int h1 = 0, c1 = 0, h2 = n-1, c2 = m-1;
    int cnt = 0;
    while(h1 <= h2 && c1 <= c2){
        for(int i = c1; i <= c2; i++){
            printf("%d ", a[h1][i]);
            ++cnt;
        }
        ++h1;
        if(cnt == n*m) break;
        for(int i = h1; i <= h2; i++){
            printf("%d ", a[i][c2]);
            ++cnt;
        }
        --c2;
        if(cnt == n*m) break;
        for(int i = c2; i >= c1; i--){
            printf("%d ", a[h2][i]);
            ++cnt;
        }
        --h2;
        if(cnt == n*m) break;
        for(int i = h2; i >= h1; i--){
            printf("%d ", a[i][c1]);
        }
        ++c1;
        if(cnt == n*m) break;
    }
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Đây là phiên bản tương tự như Approach 1 nhưng sử dụng 0-based indexing và có các kiểm tra điều kiện 'if(cnt == n*m) break;' sau mỗi hướng duyệt. Việc kiểm tra 'cnt' đảm bảo rằng chương trình dừng đúng lúc nếu tất cả các phần tử đã được in ra (đặc biệt quan trọng khi duyệt phần 'bottom to top' của vòng lặp cuối cùng, nơi có thể in xong toàn bộ phần tử trước khi vòng lặp kết thúc). Vòng lặp while 'h1 <= h2 && c1 <= c2' cũng giúp tránh các lỗi truy cập ngoài biên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng các biến boundary (top, bottom, left, right) để mô phỏng việc thu nhỏ ma trận sau mỗi vòng xoắn ốc.
• Cần kiểm tra điều kiện dừng (số phần tử đã in hoặc điều kiện biên) bên trong các vòng lặp để xử lý các trường hợp đặc biệt như ma trận 1 hàng, 1 cột hoặc ma trận vuông.

Lỗi thường gặp

• Quên kiểm tra điều kiện dừng bên trong các vòng lặp for, dẫn đến in sai thứ tự hoặc in thừa phần tử với ma trận không vuông.
• Sử dụng biến đếm vòng lặp (d) thay vì kiểm tra số phần tử đã in (cnt) hoặc điều kiện biên trực tiếp, dễ gây sai sót logic.