LeetCode 54. Spiral Matrix [Medium] [C++] 解題筆記

這題要求我們照著一個順時針的螺旋順序輸出陣列

EX:

 [ 1, 2, 3 ]        [ 1, 2, 3 ]
 [ 4, 5, 6 ]  ===>  [ 4, 5, 6 ]
 [ 7, 8, 9 ]        [ 7, 8, 9 ]

順序：紅->黃->綠->藍->紫
輸出：[1, 2, 3, 6, 9, 8, 7, 4, 5]

想法：
    可以把這個問題想像成一個走迷宮的問題，從座標(0,0)開始往順時針方向走，
只要撞牆(i.e.超出邊界)或是遇到已經走過的路就要換方向走。

作法：

           利用一個bool的二維陣列vector<vector<bool>> visited 來紀錄走過的位置，

然後用兩個array搭配來表示方向這是迷宮類問題常見的換方向的技巧。

                                       右 下 左  上

             int dir_row[4] = {0, 1, 0, -1};           

             int dir_col[4] =   {1, 0, -1, 0};

接著就只需要從(0, 0)的位置開始往右走，然後每走完一步之後判斷下一步使否撞牆或踩到走過的地方，若有則換方向走，直到走完。

完整程式碼：

class Solution {

public:

    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        if (matrix.empty()) { return {}; }

        vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));

        vector<int> res;

        int dir_row[4] = {0, 1, 0, -1};

        int dir_col[4] = {1, 0, -1, 0};

        int size = matrix.size() * matrix[0].size();

        int row = 0;

        int col = 0;

        int next_row = 0;

        int next_col = 0;

        int dir = 0;

        for (int i = 0; i < size; i++) {

            res.emplace_back(matrix[row][col]);

            visited[row][col] = true;

            next_row = row + dir_row[dir];

            next_col = col + dir_col[dir];

            if (next_row >= matrix.size() || next_row < 0 || next_col >= matrix[0].size() || next_col < 0 || visited[next_row][next_col]) {

                dir = (dir + 1) % 4;

                next_row = row + dir_row[dir];

                next_col = col + dir_col[dir];

            }

            row = next_row;

            col = next_col;

        }

       

        return res;

    }

};