Wednesday, October 29, 2014

Rotate Image

    //method 1
void rotate(vector<vector<int> > &matrix) {
        int nn=matrix.size();
        for(int layer=0;layer<nn/2;layer++){
            for(int j=layer;j<nn-layer-1;j++){
                int row=layer;int col=j;
                int tmp=matrix[row][col];
                for(int k=0;k<3;k++){
                    matrix[row][col]=matrix[nn-1-col][row];
                    int tt=row;
                    row=nn-1-col;
                    col=tt;
                }
                matrix[row][col]=tmp;
            }
        }
    }

//another flavor of method 1
void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        for(int layer=0;layer<n/2;layer++){
            for(int j=layer;j<n-layer-1;j++){
                int tmp=matrix[layer][j];
                //note that:1. the right side of the equation is the left side of the next equation
                //2. each of the equation has the form: matrix[a][b]=matrix[n-1-b][a];
                matrix[layer][j]=matrix[n-1-j][layer];
                matrix[n-1-j][layer]=matrix[n-1-layer][n-1-j];
                matrix[n-1-layer][n-1-j]=matrix[j][n-1-layer];

                matrix[j][n-1-layer]=tmp;
            }
        }
}

//method 2,from anniekim
123 -> 147 ->  741
456      258      852
789      369      963

    void rotate(vector<vector<int> > &matrix) {
        int N = matrix.size();
        for (int i = 0; i < N; ++i)
            for (int j = i+1; j < N; ++j)
                swap(matrix[i][j], matrix[j][i]);
        for (int j = 0; j < N/2; ++j)
            for (int i = 0; i < N; ++i)
                swap(matrix[i][j], matrix[i][N-j-1]);
    }

No comments:

Post a Comment