#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

vector<int>  SpiralOrder(vector<vector<int> > &matrix) 
{
	if (matrix.size() <= 0)return vector<int>();

    int row = matrix.size();
    int col = matrix[0].size(); 
    vector<int>  r;
    r.reserve(row*col);
	
	int top = 0;
	int bottom = row - 1;
	int left = 0;
	int right = col - 1;
	
	while (top < bottom && left < right)
	{
		for (int j = left; j <= right; ++j)
			r.push_back(matrix[top][j]);
		++top;
		
		for (int i = top; i <= bottom; ++i)
			r.push_back(matrix[i][right]);
		--right;
		
		for (int j = right; j >= left; --j)
			r.push_back(matrix[bottom][j]);
		--bottom;
		
		for (int i = bottom; i >= top; --i)
			r.push_back(matrix[i][left]);
		++left;
	}
	
	if (left < right && top == bottom) //for odd fat matrix
		for (int j = left; j <= right; ++j)
			r.push_back(matrix[top][j]);
	
	if (top < bottom && left == right)//for odd len matrix
		for (int i = top; i <= bottom; ++i)
			r.push_back(matrix[i][right]);
	
	if (top == bottom && left == right) //for odd sqaure matrix
		r.push_back(matrix[top][left]);
	
    return r;
}

void InitVV(vector<vector<int> >& v)
{
	int k = 0;
    for (int i = 0; i < v.size(); ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
			v[i][j] = ++k;
            cout<< setw(4) << v[i][j] << ',';
        }
		
        cout << '\n';
    }
	
    cout << endl;
}

void PrintV(vector<int> v)
{
    cout << "Spiral order:";
	for (int i = 0; i < v.size(); ++i)
    {
            cout<< setw(4) << v[i] << ',';
    }
    
    cout << endl; cout << endl;
}

int main(int argc, char** argv)
{
	vector<int> v;
	
	//Empty matrices
    /*vector<vector<int> > m(0, vector<int>(0, 0));
	InitVV(m);
    PrintV(v=SpiralOrder(m));*/
	
	//Square matrices (size_of_row == size_of_column)
    vector<vector<int> > m0(3, vector<int>(3, 0));
	InitVV(m0);
    PrintV(v=SpiralOrder(m0));
	
	//Fat matrices (size_of_row < size_of_column)
	vector<vector<int> > m1(3, vector<int>(5, 0));
	InitVV(m1);
    PrintV(v=SpiralOrder(m1));
	
	//Lean matrices (size_of_row > size_of_column)
	vector<vector<int> > m2(4, vector<int>(2, 0));
	InitVV(m2);
    PrintV(v=SpiralOrder(m2));
	

    return 0;
}