Brute force way to rotate cell one by one


  • 0
    J

    If couldn't figure out the smart reverse transpose and symmetric swap, the math way to rotate any cell in NxN matrix is
    (i, j) => (j, N - i - 1)
    It is equivalent to
    (i, j) => (N - i - 1, j) (reverse transpose) => (j, N - i - 1) (symmetric swap)
    We could have following code to rotate the whole matrix.

    class Solution {
        void rotate(int& x, int& y, int N) {
            swap(x, y);
            y = N - y - 1;
        }
        
        int setValue(vector<vector<int>>& matrix, int x, int y, int v) {
            int t = matrix[x][y];
            matrix[x][y] = v;
            return t;
        }
        
    public:
        void rotate(vector<vector<int>>& matrix) {
            const int N = matrix.size();
            const int N2 = N / 2;
            
            for (int i = 0; i < N2; i++) {
                for (int j = i; j < N - i - 1; j++) {
                    int x = i;
                    int y = j;
                    int v = matrix[x][y];
                    for (int k = 0; k < 4; k++) {
                        rotate(x, y, N);
                        v = setValue(matrix, x, y, v);
                    }
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.