void rotate(vector<vector<int> > &matrix) {

int n = matrix.size();

if(n == 0) return;

for(int i = 0; i < (n / 2); ++i) {

int top = i, bottom = n - 1 - i;

int left = top, right = bottom;

for(int j = i; j < n - 1 - i; ++j) {

int tmp = matrix[top][j];

matrix[top][j] = matrix[n - 1 - j][left];

matrix[n - 1 - j][left] = matrix[bottom][n - 1 - j];

matrix[bottom][n - 1 - j] = matrix[j][right];

matrix[j][right] = tmp;

}

}

}

reverse(matrix.begin(), matrix.end());

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

for (int j = i + 1; j < matrix[i].size(); ++j)

swap(matrix[i][j], matrix[j][i]);

}

for (auto vi : matrix) reverse(vi.begin(), vi.end());

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

for (int j = i + 1; j < matrix[i].size(); ++j)

swap(matrix[i][j], matrix[j][i]);

}

}