Spiral Matrix.txt

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> ret;
	if(matrix.empty())
		return ret;
	int left = 0, right = matrix[0].size() - 1;
	int up = 0, down = matrix.size() - 1;
	while(true)
	{
		//from left to right
		for(int i = left; i <= right; ++i)
			ret.push_back(matrix[up][i]);
		if(++up > down)return ret;
		
		//from up to down
		for(int i = up; i <= down; ++i)
			ret.push_back(matrix[i][right]);
		if(left > --right)return ret;

		//from right to left
		for(int i = right; i >= left; --i)
			ret.push_back(matrix[down][i]);
		if(up > --down)return ret;

		//from down to up
		for(int i = down; i >= up; --i)
			ret.push_back(matrix[i][left]);
		if(++left > right)return ret;
	}
}