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;
}