class Solution {

public:

	vector<int> spiralOrder(vector<vector<int>>& matrix) {

		vector<vector<int> > ve;

		int m = matrix.size();

		int n = matrix[0].size();

		vector<int> temp;

		vector<int> res;

		int i = 0, j = 0;

		for (; j < n; j++) {

			res.push_back(matrix[i][j]);

			matrix[i][j] = -111;

		}

		j -= 1;

		i += 1;

		for (; i < m; i++) {

			res.push_back(matrix[i][j]);

			matrix[i][j] = -111;

		}

		i -= 1;

		j -= 1;

        if(m == 1 || n == 1){

            return res;

        }

		for (; j >= 0; j--) {

			res.push_back(matrix[i][j]);

			matrix[i][j] = -111;

		}

		j += 1;

		i -= 1;

		for (; i >= 1; i--) {

			res.push_back(matrix[i][j]);

			matrix[i][j] = -111;

		}

		j = 1;

		i = 1;

		int direction = 1;

        if(m < 2 || n < 2) {

            return res;

        }

		while (matrix[i][j] != -111) {

			if (direction) {

				while (matrix[i][j] != -111) {

					res.push_back(matrix[i][j]);

					matrix[i][j] = -111;

					j++;

				}

				j -= 1;

				i += 1;

				while (matrix[i][j] != -111) {

					res.push_back(matrix[i][j]);

					matrix[i][j] = -111;

					i++;

				}

				i -= 1;

				j -= 1;

				direction = 0;

			}

			else {

				while (matrix[i][j] != -111) {

					res.push_back(matrix[i][j]);

					matrix[i][j] = -111;

					j--;

				}

				j += 1;

				i -= 1;

				while (matrix[i][j] != -111) {

					res.push_back(matrix[i][j]);

					matrix[i][j] = -111;

					i--;

				}

				i += 1;

				j += 1;

				direction = 1;

			}

		}

		return res;

	}

};

class Solution {

public:

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

		int n = matrix.size();

		int i = 0;

		int j = 0;

		int w = matrix.size() - 1;

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

			i = j = z;

			for (; j < w ; j++) {

				int temp = matrix[i][j];

				matrix[i][j] = matrix[n - 1 - j][i];

				matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];

				matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];

				//matrix[j][n - 1 - i] = matrix[i][j];

				matrix[j][n - 1 - i] = temp;

			}

			w -= 1; // 每次宽度减 1

		}

	}

};