之字形周遊數組

之字形周遊數組

題目要求：給丁一峰大小為m*n的矩陣，要求之字形周遊該矩陣，例如：

[[1,2,3,4],

[5,6,7,8],

[9,10,11,12]]

應該輸出[1,2,5,9,6,3,4,7,10,11,8,12];

解題思路:

給定一個矩陣，我們從第一個元素進行周遊知道最後一個元素，周遊方式無非是以下四種，

step：1

向右移動（這種移動方式隻會出現在row==0 || row == mat_rows-1;）

step2：

向右移動之後隻會出現兩種移動方式：

（1）向左下移動（row++，col–），左下移動之後，又有三種種移動方式，向下移動（col == 0）;繼續左下移動(col != 0);向右移動(row = mat_rows-1)

（2）向右上移動(row–,col++)，右上移動之後，又有兩種移動方式,向下移動（col == mat_cols-1）,繼續向右上移動;向右移動（row==0）

這樣我們就周遊了所有的移動方式.

下面我們直接貼代碼：

vector<int> zigzagScan(vector<vector<int>> &matrix)
{
    vector<int> result;
    //當矩陣中的元素為空或者隻有一個元素的時候的異常處理
    if (matrix.size() ==  || matrix[].size() == )
    {
        return matrix[];
    }
    //當矩陣中的元素隻有一列的時候,直接傳回所有元素
    if (matrix[].size() == )
    {
        for (size_t i = ; i < matrix.size(); i++)
        {
            result.push_back(matrix[i][]);
        }
        return result;
    }
    //定義矩陣的行數
    int mat_rows = matrix.size();
    //定義矩陣的列數
    int mat_cols = matrix[].size();
    int row = , col = ;
    //第一行的第一個元素是向右移的
    Move move = moveToRight;
    //row = n-1&&col = n-1的情況在while循環結束後處理，防止出現越界的情況
    while (row != mat_rows -  || col != mat_cols - )
    {
        //将每個元素依次壓入到數組中去
        cout << matrix[row][col] << ' ';
        result.push_back(matrix[row][col]);
        switch (move)
        {
        case moveToRight:
            col++;
            if (row == )
                move = moveToBottomLeft;
            else
                move = moveToTopRight;
            break;
        case moveToTopRight:
            row--;
            col++;
            if (row ==  && col != mat_cols - )
                move = moveToRight;
            else if (col == mat_cols - )
                move = moveToBottom;
            else
                move = moveToTopRight;
            break;
        case moveToBottom:
            row++;
            if (col == )
                move = moveToTopRight;
            else
                move = moveToBottomLeft;
            break;
        case moveToBottomLeft:
            row++;
            col--;
            if (col ==  && row != mat_rows - )
                move = moveToBottom;
            else if (row == mat_rows - )
                move = moveToRight;
            else
                move = moveToBottomLeft;
            break;
        }
    }
    cout << matrix[mat_rows - ][mat_cols-] << ' ';
    result.push_back(matrix[mat_rows - ][mat_cols - ]);
    return result;
}