#pragma warning(disable:4996)

#include <Windows.h>
#include <tchar.h>
#include <cstdio>
#include <vector>
using namespace std;

/*
	submit time : 1	  // But I don‘t know how to deal with "Follow up"
	request :
		You are given an n x n 2D matrix representing an image.

		Rotate the image by 90 degrees (clockwise).

		/☆☆☆☆☆☆☆☆☆☆☆Have no idea☆☆☆☆☆☆☆☆☆☆☆/
		/☆☆	Follow up:					 ☆☆/
		/☆☆	Could you do this in-place?  ☆☆/
		/☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆/
*/

void rotate(vector<vector<int> > &matrix) {
	int n = matrix.size();
	if (n <= 1) return;

	// use extra space
	int** tempMatrix = new int*[n];
	for (int i = 0; i < n; ++i)
		tempMatrix[i] = new int[n];

	int column = n - 1;
	vector<vector<int> >::iterator iter = matrix.begin();
	for (; iter != matrix.end(); ++iter) {
		for (int row = 0; row < n; ++row)
			tempMatrix[row][column] = (*iter)[row];
		--column;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			matrix[i][j] = tempMatrix[i][j];
	}

	for (int i = 0; i < n; ++i)
		delete[] tempMatrix[i];
	delete[] tempMatrix;
}

//===================Test====================
void printMatrix(vector<vector<int> >& matrix) {
	for (vector<vector<int> >::iterator iterI = matrix.begin(); iterI != matrix.end(); ++iterI) {
		for (vector<int>::iterator iterII = (*iterI).begin(); iterII != (*iterI).end(); ++iterII) {
			printf("%5d ", *iterII);
		}
		printf("\n");
	}
	printf("\n");
}

void Test(vector<vector<int> >& matrix) {
	printf("Original:\n");
	printMatrix(matrix);
	rotate(matrix);
	printf("Now:\n");
	printMatrix(matrix);
}

void Test1() {
	int row1[] = { 15, 31, 25, 1, 2 };
	int row2[] = { 26, 11, 4, 7, 25 };
	int row3[] = { 3, 21, 101, 99, 78 };
	int row4[] = { 51, 14, 18, 22, 92 };
	int row5[] = { 11, 131, 4, 1, 37 };
	vector<int> vec1(row1, row1 + sizeof(row1) / sizeof(int));
	vector<int> vec2(row2, row2 + sizeof(row2) / sizeof(int));
	vector<int> vec3(row3, row3 + sizeof(row3) / sizeof(int));
	vector<int> vec4(row4, row4 + sizeof(row4) / sizeof(int));
	vector<int> vec5(row5, row5 + sizeof(row5) / sizeof(int));
	vector<vector<int> > matrix;
	matrix.push_back(vec1);
	matrix.push_back(vec2);
	matrix.push_back(vec3);
	matrix.push_back(vec4);
	matrix.push_back(vec5);
	Test(matrix);
}

void Test2() {
	int row1[] = { 15, 31 };
	int row2[] = { 26, 11 };
	vector<int> vec1(row1, row1 + sizeof(row1) / sizeof(int));
	vector<int> vec2(row2, row2 + sizeof(row2) / sizeof(int));
	vector<vector<int> > matrix;
	matrix.push_back(vec1);
	matrix.push_back(vec2);
	Test(matrix);
}

void Test3() {
	int row1[] = { 15 };
	vector<int> vec1(row1, row1 + sizeof(row1) / sizeof(int));
	vector<vector<int> > matrix;
	matrix.push_back(vec1);
	Test(matrix);
}

int _tmain(int argc, _TCHAR* argv[]) {
	Test1();
	Test2();
	Test3();

	system("pause");
	return 0;
}