面试题29：顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

思路很简单：用一个循环打印矩阵，每次循环打印矩阵中的一圈。把打印一圈分为4步：

从左到右打印上边一行；
从上往下打印右边一列；
从右往左打印下边一行；
从下往上打印左边一列。
不过得注意的是，当行数或列数为奇数时，可能最后一圈就只剩下一行或者一列了。因此如果按上面的步骤会重复打印最后一行或一列。所以在3,4步得判断避免重复打印最后一行或一列。
当行数为奇数时，最后一圈就是一行，所以只用执行1，不用执行3，故在3中加上判断语句rows - 2 * circle != 1；
当列数为奇数时，最后一圈就是一列，所以只用执行2，不用执行4，故在4中加上判断语句cols - 2 * circle != 1。
写了顺时针和逆时针两种代码：

/*
* 1.计算要打印的圈数；
* 2.每一圈按照四个方向打印，注意起点与终点的坐标：上面一行从左到右，右边一列从上到下，底边一行由右到左，左边一列从下到上
* 3.最后若行数为奇数，则最后一圈只有一行；若列数为奇数，则最后一圈只有一列。这种情况得加判断条件
*/

//顺时针打印矩阵
vector<int> printMatrix(vector<vector<int> > matrix)
{
    vector<int> result;
    if (matrix.size() == 0)
        return result;
    //1.求出要打印的圈数
    int rows = matrix.size(), cols = matrix[0].size();
    int circles = (min(rows, cols) + 1) / 2;
    //2.分圈打印
    for (int circle = 0; circle < circles; ++circle)
    {
        //从左到右打印第一行
        for (int j = circle; j <= cols-1-circle; ++j)
        {
            result.push_back(matrix[circle][j]);
        }
        //从上到下打印右边一列
        for (int i = circle + 1; i <= rows -1- circle; ++i)
        {
            result.push_back(matrix[i][cols - 1 - circle]);
        }

        //为了保证行数或列数为奇数时不重复打印一行或一列，在两步得加判断条件
        if (rows-circle * 2 !=1 && cols - circle * 2 != 1)
        {
            //从右向左打印底下一行
            for (int j = cols - 2 - circle; j >= circle; --j)
            {
                result.push_back(matrix[rows - 1 - circle][j]);
            }
            //从下往上打印左边一列
            for (int i = rows - 2 - circle; i >= circle + 1; --i)
            {
                result.push_back(matrix[i][circle]);
            }
        }
    }
    return result;
}

//逆时针打印矩阵
vector<int> printMatrixAntiClockWise(vector<vector<int> > matrix)
{
    vector<int> result;
    if (matrix.size() == 0)
        return result;
    int rows = matrix.size(), cols = matrix[0].size();
    int circles = (min(rows, cols) + 1) / 2;
    for (int circle = 0; circle < circles; ++circle)
    {
        //从上往下打印左边一列
        for (int i = circle; i <= rows - 1 - circle; ++i)
        {
            cout << "1";
            result.push_back(matrix[i][circle]);
        }
        cout << endl;
        //从左往右打印底部一行
        for (int j = circle + 1; j <= cols - 1 - circle; ++j)
        {
            cout << "2";
            result.push_back(matrix[rows - 1 - circle][j]);
        }
        cout << endl;
        if (cols - 2 * circle != 1 && rows - 2 * circle != 1)
        {
            //从下往上打印右边一列
            for (int i = rows - 2 - circle; i >= circle; --i)
            {
                cout << "3";
                result.push_back(matrix[i][cols - 1 - circle]);
            }
            cout << endl;
            //从右往左打印上边一行
            for (int j = cols - 2 - circle; j >= circle + 1; --j)
            {
                cout << "4";
                result.push_back(matrix[circle][j]);
            }
            cout << endl;
        }

    }
    return result;
}

int main()
{
    //vector<vector<int> > matrix = { {1,2,3,4,5},{6,7,8,9,10}, {11,12,13,14,15}, {16,17,18,19,20} };
    vector<vector<int> > matrix = { {1,2,3,4,5},{6,7,8,9,10}, {11,12,13,14,15} };
    vector<int> result = printMatrixAntiClockWise(matrix);
    for (int i = 0; i < result.size(); ++i)
    {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}