#include <vector>
#include <iostream>
using namespace std;

/*
**  Explanation of First solution:
**
**  1   2   3   4
**  5   6   7   8
**  9   10  11  12
**  13  14  15  16
**
**  The layers mean the square cycles from outer to inner.
**  1,2,3,4,8,12,16,15,14,13,9,5 is one layer, 6,7,11,10 is another layer
**  To rotate the matrix, is just to rotate the layers
**  
**  The rule for rotating is easy to fiqure out:
**  regard: 
**      2 -> 8 -> 15 -> 9 -> 2
**  it is:
**      a[i][j] -> a[m-j][i] -> a[m-i][m-j] -> a[j][m-i] -> a[i][j]
**  where m is max index of row/col, which begin at 0
*/ 
void RotateMatrix(vector<vector<int> > &matrix)
{
    size_t m = matrix.size() -1;

    if (m <= 0) return;
    for (int i = 0; i <= m/2; ++i)//go over each layer
        for (int j = i; j < m-i; ++j) //rotate the layer
        {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[m-j][i];
            matrix[m-j][i] = matrix[m-i][m-j];
            matrix[m-i][m-j] = matrix[j][m-i];
            matrix[j][m-i] = tmp;
        }
}

/*
**  Explanation of Second solution:
**  
**      Concern following manipulation is easy:
**          flip up to down
**          flip left to right
**          flip over diagonal line
**              (there are two diagonal lines: 
**                      positive, which is from top-left to down-right; 
**                      negative, which is from top-right to down-left)
**
**      Any rotation could be a combination of above manipluation.
**      Rotate 90 degree clockwise is just:
**          filp over positive diagonal line, then flip left to righ.
**
**      This is not only combination, you could figure out other ways.
*/



void RotateWithFlip(vector<vector<int> >& matrix)
{
    int m = matrix.size()-1;
	
    //flip over positive diagonal line
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j < i; ++j)
        {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }

    //flip left to right
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j < (m+1)/2; ++j)
        {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][m-j];
            matrix[i][m-j] = tmp;
        }
}



void PrintVV(vector<vector<int> >& m)
{
    for (size_t i = 0; i < m.size(); ++i)
    {
        vector<int>& v = m[i];
        for (size_t j = 0; j < v.size(); ++j)
            cout << v[j] <<",\t";
        
        cout << '\n'; 
    }
	cout << '\n';
}


int main(int argc, char** argv)
{
    int k = 0;
    int n = 5;
    vector<vector<int> > m;
    for (int i = 0; i < n; ++i)
    {
        vector<int> v;
        for (int j = 0; j < n; ++j)
            v.push_back(++k);

        m.push_back(v);
    }
	
    PrintVV(m);
    //RotateWithFlip(m);
	RotateMatrix(m);
    PrintVV(m);
    return 0;
}