In ma trận theo xoắn ốc (Print Matrix in spiral way)

Thuật toán này dùng để in các phần tử mảng theo thứ tự xoắn ốc. Bắt đầu từ hàng đầu tiên, in toàn bộ nội dung rồi theo cột cuối, hàng cuối, v.v., in các phần tử theo kiểu xoắn ốc.

Độ phức tạp thời gian của thuật toán là O(MN), M là số hàng, N là số cột.

Đầu vào và Đầu ra

Đầu vào: Ma trận: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Đầu ra: Nội dung mảng theo dạng xoắn ốc: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 15 16

Thuật toán

dispSpiral(mat, m, n)

Đầu vào: Ma trận mat, số hàng và cột m, n.

Đầu ra: In các phần tử ma trận theo xoắn ốc.

Begin
    currRow := 0 and currCol := 0
    while currRow and currCol trong phạm vi ma trận, do
        for i từ currCol đến n-1, do
            display mat[currRow, i]
        done
        tăng currRow lên 1
        for i từ currRow đến m-1, do
            display mat[i, n-1]
        done
        giảm n đi 1
        if currRow < m, then
            for i := n-1 down to currCol, do
                display mat[m-1, i]
            done
            giảm m đi 1
        if currCol < n, then
            for i := m-1 down to currRow, do
                display mat[i, currCol]
            done
            tăng currCol lên 1
    done
End

Ví dụ (C++)

#include 
#define ROW 3
#define COL 6
using namespace std;
int array[ROW][COL] = {
    {1, 2, 3, 4, 5, 6},
    {7, 8, 9, 10, 11, 12},
    {13, 14, 15, 16, 17, 18}
};
void dispSpiral(int m, int n) {
    int i, currRow = 0, currCol = 0;
    while (currRow < ROW && currCol < COL) {
        for (i = currCol; i < n; i++) {
            cout << array[currRow][i] << " ";
        }
        currRow++;
        for (i = currRow; i < m; ++i) {
            cout << array[i][n-1] << " ";
        }
        n--;
        if (currRow < m) {
            for (i = n-1; i >= currCol; --i) {
                cout << array[m-1][i] << " ";
            }
            m--;
        }
        if (currCol < n) {
            for (i = m-1; i >= currRow; --i) {
                cout << array[i][currCol] << " ";
            }
            currCol++;
        }
    }
}
int main() {
    dispSpiral(ROW, COL);
}

Đầu ra

1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 15 16