leecode 解题总结：48. Rotate Image

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
/*
问题:
You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

分析:
这个是程序员面试经典的一道题目。题目本意是将n*n的矩阵顺时针旋转90度。
参见下图，主要想法是：将111旋转到222的位置，222旋转到333的位置，333旋转444的位置，444旋转到111的位置.
同理：将5旋转到6,6旋转到7,...
1112
4562
4872
4333
问题的关键变成:如何确定上边到右边，右边到下边，下边到左边，左边到右边的坐标映射关系。
上边到右边:特点,原先上边横坐标一致，变换到右边后，纵坐标一致。
设置len(每次矩阵长度).offset:起点偏移值，从0开始,len + offset是最大纵坐标长度
(0,0),(0,1),(0,2)， 变换成(0,3),(1,3),(2,3)
所以上边(x,y),变换为右边(y,len + offset)

右边变下边:
(0,3),(1,3),(2,3) 变为(3,3),(3,2),(3,1),右边(x,len+offset)变成下边(len + offset, )

下边变左边:
(3,3),(3,2),(3,1) 变为(1,0),(2,0),(3,0)
下边是

左边变上边:
(1,0),(2,0),(3,0) 变为
(0,2),(0,1),(0,0)

如果当前长度为n-1,下一次旋转的小矩阵长度为n-3(减去两边各1个)
第一次旋转矩阵上边起始位置为:0~n-2,
  二                        :1~n-3

//控制循环次数
int offset = -1;
for(int len = n -1 ; len >= 0 ; len -= 2)
{
    //决定左上角起点的横坐标
	offset++;
	for(int i = offset; i < offset + len ; i++)
	{
		//进行变换处理
	}
}

正确变换顺序是: 
临时=右边
右边=上边
上边=左边
左边=下边
下边=临时

输入
2
5 6
8 7

3
1 2 3
4 5 6
7 8 9

4
1 1 1 2
4 5 6 2
4 8 7 2
4 3 3 3
输出:
8 5
7 6

7 4 1
8 5 2
9 6 3

4 4 4 1
3 8 5 1
3 7 6 1
3 2 2 2

关键:
1 简单方法：
图像旋转先从上到下每一行逆置，然后对称元素互换即可
 * 1 2 3     7 8 9     7 4 1
 * 4 5 6  => 4 5 6  => 8 5 2
 * 7 8 9     1 2 3     9 6 3
2 旋转方法
	for(int len = n ; len > 0 ; len -= 2)
	{
		//决定左上角起点的纵坐标，起始横坐标也一样。因为是矩阵
		offset++;
		border = offset + len - 1;
		count = 0;
		//这个边界有问题,len是矩阵长度:[0,3),[1,2)，最后一个元素无需反转
		for(int j = offset; j < border; j++)
		{
			//临时 = 右边
			temp = matrix.at(j).at(border) ;

			//右边 = 上边, 右边: (0,3),(1,3),(2,3) (j,border)，上边:(0,0),(0,1),(0,2),即(offset,j) ,
			//右边:(1,2)，上边：(1,1)
			matrix.at(j).at(border) = matrix.at(offset).at(j);

			//上边 = 左边，上边:(0,0),(0,1),(0,2),即(offset,j) ，左边:(3,0),(2,0),(1,0),(border - count ,offset),
			//上边:(1,1)，左边:(2,1)，易错这里用count确保初始border-count一定是为边界，如果border-j就不是边界
			matrix.at(offset).at(j) = matrix.at(border - count).at(offset);

			// 左边 = 下边，左边:(3,0),(2,0),(1,0),(border -j,offset)，下边:(3,3),(3,2),(3,1)即(border , border -j)
			//左边:(2,1)，下边:(2,2)
			matrix.at(border - count).at(offset) =  matrix.at(border).at(border - count ) ;

			//下边 = 右边，下边:(3,3),(3,2),(3,1)，即(border , border - j)，
			matrix.at(border).at(border - count) = temp;
			count++;
		}
	}
}


*/

void swap(int* num1 , int* num2)
{
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
		if(matrix.empty())
		{
			return ;
		}
		int n = matrix.size();
		//上下逆置
		reverse(matrix.begin() , matrix.end());
		//对称元素互换
		int size;
		for(int i = 0 ; i < n ; i++)
		{
			size = matrix.at(i).size();
			for(int j = i + 1 ; j < size ; j++)
			{
				swap(matrix[i][j] , matrix[j][i]);
			}
		}
	}

    void rotate2(vector<vector<int>>& matrix) {
		if(matrix.empty())
		{
			return ;
		}
		int n = matrix.size();
		int offset = -1;
		int border;//边界
		int temp;
		int count;
		for(int len = n ; len > 0 ; len -= 2)
		{
			//决定左上角起点的纵坐标，起始横坐标也一样。因为是矩阵
			offset++;
			border = offset + len - 1;
			count = 0;
			//这个边界有问题,len是矩阵长度:[0,3),[1,2)，最后一个元素无需反转
			for(int j = offset; j < border; j++)
			{
				//临时 = 右边
				temp = matrix.at(j).at(border) ;

				//右边 = 上边, 右边: (0,3),(1,3),(2,3) (j,border)，上边:(0,0),(0,1),(0,2),即(offset,j) ,
				//右边:(1,2)，上边：(1,1)
				matrix.at(j).at(border) = matrix.at(offset).at(j);

				//上边 = 左边，上边:(0,0),(0,1),(0,2),即(offset,j) ，左边:(3,0),(2,0),(1,0),(border - count ,offset),
				//上边:(1,1)，左边:(2,1)，易错这里用count确保初始border-count一定是为边界，如果border-j就不是边界
				matrix.at(offset).at(j) = matrix.at(border - count).at(offset);

				// 左边 = 下边，左边:(3,0),(2,0),(1,0),(border -j,offset)，下边:(3,3),(3,2),(3,1)即(border , border -j)
				//左边:(2,1)，下边:(2,2)
				matrix.at(border - count).at(offset) =  matrix.at(border).at(border - count ) ;

				//下边 = 右边，下边:(3,3),(3,2),(3,1)，即(border , border - j)，
				matrix.at(border).at(border - count) = temp;
				count++;
			}
		}
    }
};

void print(vector< vector<int> >& matrix)
{
	if(matrix.empty())
	{
		cout << "no result" << endl;
		return ;
	}
	int size = matrix.size();
	for(int i = 0 ; i < size ; i++)
	{
		for(int j = 0 ; j < size ; j++)
		{
			cout << matrix.at(i).at(j) << " ";
		}
		cout << endl;
	}
}

void process()
{
	int num;
	int value;
	vector<vector<int> > matrix;
	Solution solution;
	while(cin >> num)
	{
		matrix.clear();
		for(int i = 0 ; i < num ; i++)
		{
			vector<int> nums;
			for(int j = 0 ; j < num ; j++)
			{
				cin >> value;
				nums.push_back(value);
			}
			matrix.push_back(nums);
		}
		solution.rotate(matrix);
		print(matrix);
	}
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}