题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

样例

输入：
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

输出：[1,2,3,4,8,12,11,10,9,5,6,7]

递归算法

递归按顺时针访问矩阵的元素并保存在结果中。

时间复杂度O(mn)

C++ 代码

class Solution {
public:

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

    void visit(vector<int>& res, vector<vector<bool>>& st, vector<vector<int>>& matrix, int x, int y, int d){
        res.push_back(matrix[x][y]);
        st[x][y] = true;
        int cnt = 0;
        for(int i = d; cnt < 4; i = (i + 1)%4){ // 将过来的方向作为本次的起始方向
            int xx = x + dx[i], yy = y + dy[i];
            if(xx >= 0 && xx < matrix.size() && yy >= 0 && yy < matrix[0].size() && !st[xx][yy]){
                visit(res, st, matrix, xx, yy, i);
            }
            cnt ++;
        }
        return;
    }

    vector<int> printMatrix(vector<vector<int> > matrix) {

        if(!matrix.size() || !matrix[0].size()) return {};

        vector<int> res;
        vector<vector<bool>> st(matrix.size(), (vector<bool>(matrix[0].size())));

        visit(res, st, matrix, 0, 0, 0);

        return res;
    }
};