# 48 - Rotate Image

這種題目的思考方式：

1. 想想目標位置和原本位置之間的關係

   寫下來之後，就會發現只是把原本的行，變成新的列

   
2. 寫下轉換方法

   有了第一步之後，我們就可以來想要怎麼做到。

   在矩陣運算中，有個很常用的操作是對稱的變換 - a[i][j] = a[j][i]，如果我們能用這樣的操作，就不需要花額外的空間來儲存。

   如果我們看最後結果，並根據左上右下對角線取對稱，就會得到原本矩陣的列對稱結果：

   7 4 1    7 8 9 
   8 5 2 => 4 5 6 
   9 6 3    1 2 3

所以我們只要先對列做一次對稱，再以對角線取對稱一次就可以了：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        reverse(matrix.begin(), matrix.end());

        for(int i=0; i<matrix.size(); i++) {
            for(int j=i+1; j<matrix[i].size(); j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

順便附上一個整理：

/*
 * clockwise rotate
 * first reverse up to down, then swap the symmetry 
 * 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
*/
void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

/*
 * anticlockwise rotate
 * first reverse left to right, then swap the symmetry
 * 1 2 3     3 2 1     3 6 9
 * 4 5 6  => 6 5 4  => 2 5 8
 * 7 8 9     9 8 7     1 4 7
*/
void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}