#pragma warning(disable:4996)

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

/*
	submit time : 2
		1. Runtime Error
			[]
	request :
		Given a matrix of m x n elements (m rows, n columns), 
			return all elements of the matrix in spiral order.

		For example,
		Given the following matrix:

		[
		[ 1, 2, 3 ],
		[ 4, 5, 6 ],
		[ 7, 8, 9 ]
		]
		You should return [1,2,3,6,9,8,7,4,5].
*/

vector<int> spiralOrder(vector<vector<int> > &matrix) {
	vector<int> vSpiral;
	int rows = matrix.size();
	if (rows == 0) return vSpiral;
	int columns = matrix[0].size();
	int cnt = rows*columns;

	int** matrix01 = new int*[rows];
	for (int i = 0; i < rows; ++i)
		matrix01[i] = new int[columns];
	for (int i = 0; i < rows;++i)
		for (int j = 0; j < columns; ++j)
			matrix01[i][j] = 0;

	int row = 0, column = 0;
	while (cnt) {
		// move right
		while (column < columns && !matrix01[row][column]) {
			vSpiral.push_back(matrix[row][column]);
			matrix01[row][column] = 1;
			++column;
			--cnt;
		}
		--column;
		++row;
		// move down
		while (row < rows && !matrix01[row][column]) {
			vSpiral.push_back(matrix[row][column]);
			matrix01[row][column] = 1;
			++row;
			--cnt;
		}
		--row;
		--column;
		// move left
		while (column >= 0 && !matrix01[row][column]) {
			vSpiral.push_back(matrix[row][column]);
			matrix01[row][column] = 1;
			--column;
			--cnt;
		}
		++column;
		--row;
		// move up
		while (row >= 0 && !matrix01[row][column]) {
			vSpiral.push_back(matrix[row][column]);
			matrix01[row][column] = 1;
			--row;
			--cnt;
		}
		++row;
		++column;
	}

	return vSpiral;
}

//=================Test==================
void printVector_int(vector<int>& vec) {
	vector<int>::iterator iter = vec.begin();
	printf("[");
	for (; iter != vec.end(); ++iter)
		printf("%d ", *iter);
	printf("]\n");
}

void Test(vector<vector<int> >& matrix) {
	vector<int> result = spiralOrder(matrix);
	printVector_int(result);
}

void Test1() {
	int row1[] = { 1, 2, 3 };
	int row2[] = { 4, 5, 6 };
	int row3[] = { 7,8,9 };
	int row4[] = { 10,11,12 };
	vector<vector<int> > matrix;
	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));
	matrix.push_back(vec1);
	matrix.push_back(vec2);
	matrix.push_back(vec3);
	matrix.push_back(vec4);
	Test(matrix);
}

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

	system("pause");
	return 0;
}