剑指Offer(T20)顺时针打印矩阵

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解题思路

循环地进行从左到右，从上到下，从右到左，从下到上的打印“年轮”上的元素。

难点

• 怎么确定循环条件
  （1）每一圈打印的起始点都在45°对角线上，所以可以声明一个start变量标识起始打印点
  （2）由于(start+1)代表已经打印的圈数，2*max{start} < min{rows,columns}

• 怎么确定四条边的打印前提条件
  从左到右：子矩阵至少有一个元素
  从上到下：子矩阵至少有两列
  从右到左：子矩阵至少有两行两列
  从下到上：子矩阵至少有三行两列

• 怎样访问四条边上元素
  由于四条边的元素，一旦起始点定了之后，其他所有元素的行标和列标范围也就定了，因此可以确定endX,endY
  endX = columns - 1 - start
  endY = rows - 1 - start
  从左到右遍历时，纵坐标保持变为y = start，横坐标为x = start:1:endX
  从上到下遍历时，横坐标保持不变x = endX,纵坐标为y = (start+1):1:endY
  从右到左，y = endY, x = (endX-1):1:start
  从下到上，x = start, y = (endY-1):1:(start+1)

有意思的地方

四条边的打印前提条件具有递进关系而非并列关系，即一个比一个条件更苛刻

​class Solution {
public:
    void PrintMatrixInCircle(vector<vector<int> > &matrix,int start, vector<int> &ret){
        int rows = (int)matrix.size();
        int columns = (int)matrix[0].size();
        int endX = (columns-1) - start;
        int endY = (rows-1) - start;
        // 从左到右
        for(int i = start; i <= endX; ++i){
            ret.push_back(matrix[start][i]);
        }
        
        // 从上到下，至少2行
        if(endY > start){
            for(int i = start+1;i <= endY;++i){
                ret.push_back(matrix[i][endX]);
            }
        }
        
        // 从右到左，至少2行2列
        if(endX > start && endY > start){
            for(int i = endX-1; i >= start; --i){
                ret.push_back(matrix[endY][i]);
            }
        }
        
        // 从下到上，至少有3行2列
        if(endY > start + 1 && endX > start){
            for(int i = endY-1; i >= start + 1; i--){
                ret.push_back(matrix[i][start]);
            }
        }
    }
    
    
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int rows = (int)matrix.size();
        int columns = (int)matrix[0].size();
        vector<int> ret;
        if(matrix.size() == 0 || columns <=0 || rows <= 0) return ret;
        int start = 0;
        while(columns > start*2 && rows > start*2){
            PrintMatrixInCircle(matrix,start,ret);
            ++start;
        }
        
        return ret;
    }
};