Cấu trúc dữ liệu và Giải thuật Bài 15: Duyệt ma trận: Theo đường chéo, hình xoắn ốc (Spiral Matrix).

Duyệt ma trận theo từng hàng hay từng cột là thao tác cơ bản, nhưng các bài toán thực tế (và đặc biệt là các vòng phỏng vấn tại các công ty công nghệ) thường yêu cầu bạn phải di chuyển qua lưới dữ liệu 2D theo những quỹ đạo phức tạp hơn. Hai quỹ đạo kinh điển nhất để rèn luyện kỹ năng thao tác với chỉ mục (index manipulation) chính là duyệt theo đường chéo và duyệt theo hình xoắn ốc.

1. Duyệt ma trận theo đường chéo (Diagonal Traversal)

Trong một ma trận vuông kích thước $N \times N$ , chúng ta có hai đường chéo quan trọng mang những đặc tính toán học cực kỳ thú vị:

Đường chéo chính (Main Diagonal): Chạy từ góc trên bên trái xuống góc dưới bên phải.
- Đặc điểm: Chỉ số hàng luôn bằng chỉ số cột ( $i = j$ ).
- Ví dụ: (0,0), (1,1), (2,2)...
Đường chéo phụ (Anti-Diagonal): Chạy từ góc trên bên phải xuống góc dưới bên trái.
- Đặc điểm: Tổng của chỉ số hàng và chỉ số cột luôn bằng $N - 1$ ( $i + j = N - 1$ ). Từ đó suy ra $j = (N - 1) - i$ .
- Ví dụ ( $N=3$ ): (0,2), (1,1), (2,0).

Cạm bẫy $O(N^2)$ :

Người mới học thường dùng hai vòng lặp lồng nhau duyệt qua toàn bộ ma trận, thêm câu lệnh rẽ nhánh if (i == j) để in ra phần tử đường chéo. Cách này ngốn $O(N^2)$ thời gian để kiểm tra những ô nhớ hoàn toàn không liên quan, cực kỳ lãng phí tài nguyên CPU.

Tối ưu hóa $O(N)$ :

Bằng cách sử dụng đặc tính toán học trên, chúng ta chỉ cần đúng một vòng lặp để trích xuất cả hai đường chéo trực tiếp từ RAM.

func printDiagonals(matrix [][]int, n int) {
    // Chỉ mất O(N) thời gian, nhảy thẳng đến đúng ô nhớ cần thiết
    for i := 0; i < n; i++ {
        fmt.Printf("Đường chéo chính: %d\n", matrix[i][i])
        fmt.Printf("Đường chéo phụ: %d\n", matrix[i][n - 1 - i])
    }
}

2. Duyệt ma trận hình xoắn ốc (Spiral Matrix)

Đây là bài toán LeetCode Medium (Bài 54) cực kỳ nổi tiếng. Yêu cầu: Trả về tất cả phần tử của một ma trận $M \times N$ theo thứ tự xoắn ốc từ ngoài vào trong (Phải $\rightarrow$ Xuống $\rightarrow$ Trái $\rightarrow$ Lên).

Bản chất của bài toán: Đây không phải là bài toán đòi hỏi thuật toán cao siêu, mà là bài toán thử thách khả năng quản lý ranh giới (Boundary Management).

Hãy tưởng tượng ma trận như một bức tường. Mỗi lần bạn đi hết một cạnh viền ngoài, bức tường ở cạnh đó sẽ "thu hẹp" lại 1 nấc. Để lập trình được, bạn cần thiết lập 4 "bức tường" vô hình kiểm soát không gian:

top: Ranh giới trên cùng (Khởi tạo: 0)
bottom: Ranh giới dưới cùng (Khởi tạo: M - 1)
left: Ranh giới bên trái (Khởi tạo: 0)
right: Ranh giới bên phải (Khởi tạo: N - 1)

Logic di chuyển vòng lặp:

Đi từ Trái sang Phải: Duyệt hàng top từ cột left đến right. Sau khi đi xong, ép bức tường top xuống 1 nấc (top++).
Đi từ Trên xuống Dưới: Duyệt cột right từ hàng top đến bottom. Đi xong, ép tường right sang trái 1 nấc (right--).
Đi từ Phải sang Trái: Duyệt hàng bottom từ cột right lùi về left. Đi xong, ép tường bottom lên trên 1 nấc (bottom--).
Đi từ Dưới lên Trên: Duyệt cột left từ hàng bottom lùi về top. Đi xong, ép tường left sang phải 1 nấc (left++).

Vòng lặp sẽ tiếp tục cuộn vào trong cho đến khi các bức tường đụng nhau (top > bottom hoặc left > right).

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }
    
    var result []int
    top, bottom := 0, len(matrix) - 1
    left, right := 0, len(matrix[0]) - 1
    
    for top <= bottom && left <= right {
        // 1. Đi từ Trái -> Phải (Dọc theo bức tường top)
        for j := left; j <= right; j++ {
            result = append(result, matrix[top][j])
        }
        top++ // Thu hẹp ranh giới trên
        
        // 2. Đi từ Trên -> Dưới (Dọc theo bức tường right)
        for i := top; i <= bottom; i++ {
            result = append(result, matrix[i][right])
        }
        right-- // Thu hẹp ranh giới phải
        
        // Cần kiểm tra lại ranh giới để tránh in trùng lặp khi ma trận không vuông (như 3x4)
        if top <= bottom {
            // 3. Đi từ Phải -> Trái (Dọc theo bức tường bottom)
            for j := right; j >= left; j-- {
                result = append(result, matrix[bottom][j])
            }
            bottom-- // Thu hẹp ranh giới dưới
        }
        
        if left <= right {
            // 4. Đi từ Dưới -> Lên (Dọc theo bức tường left)
            for i := bottom; i >= top; i-- {
                result = append(result, matrix[i][left])
            }
            left++ // Thu hẹp ranh giới trái
        }
    }
    
    return result
}

3. Ứng dụng thực tế của tư duy duyệt không gian 2D

Đứng ở góc độ kỹ thuật phần mềm, khả năng điều hướng lưới 2D là nền tảng cho nhiều hệ thống phức tạp:

Phân mảnh dữ liệu không gian (Spatial Partitioning): Việc lưu trữ dữ liệu địa lý, vẽ bản đồ hoặc tìm kiếm tài xế xung quanh tọa độ hiện tại đòi hỏi các kỹ thuật điều hướng mảng 2D thông minh như Z-Order Curve hay Geohash (bản chất là các quỹ đạo đệ quy/xoắn ốc) để tối ưu hóa truy vấn Database.
Xử lý ảnh (Image Processing) & CNN: Các bộ lọc (filters/kernels) trong mạng nơ-ron tích chập AI quét qua các ma trận điểm ảnh (pixels) bằng cách điều khiển các vòng lặp đa chiều để nhận diện biên độ viền, đặc điểm khuôn mặt hoặc làm mờ ảnh.
Phát triển Game (Game Development): Khi render một bản đồ dạng Isometric (như Đế chế), thuật toán đồ họa phải duyệt qua một ma trận 2D theo các đường chéo để vẽ vật thể từ xa đến gần, đảm bảo các tòa nhà không bị đè lên nhau sai luật phối cảnh.

Thành thạo di chuyển linh hoạt trên Mảng 2D là một mốc quan trọng. Ở bài học tiếp theo, chúng ta sẽ quay trở lại với Mảng 1D nhưng được vũ trang thêm một kỹ thuật toán học cực kỳ mạnh mẽ: Kỹ thuật giúp bạn tính tổng hàng triệu bản ghi trong đúng một nhịp $O(1)$ .

cấu trúc dữ liệu

1. Duyệt ma trận theo đường chéo (Diagonal Traversal)

2. Duyệt ma trận hình xoắn ốc (Spiral Matrix)

3. Ứng dụng thực tế của tư duy duyệt không gian 2D

Table of contents