Friday, 6 July 2012

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?




INPUT  >   OUTPUT        INPUT    >  >    OUTPUT  
4                                        4                                         
1 2 3 4        1 1 1 1           11 12 13 14      41 31 21 11
1 2 3 4        2 2 2 2           21 22 23 24      42 32 22 12
1 2 3 4        3 3 3 3           31 32 33 34      43 33 23 13
1 2 3 4        4 4 4 4           41 42 43 44      44 34 24 14



#include<stdio.h>
void rotate(int I[10][10],int O[10][10],int j,int i)
{
    int k,l,temp;
    for(k=0;k<j;k++)
    {
        temp=I[k+i][i];              // copy of Left in temp
        O[k+i][i]=I[i+j-1][i+k];     // copy bottom to left
        O[i+j-1][i+k]=I[i+j-k-1][i+j-1];   // copy right to bottom
        O[i+j-k-1][i+j-1]=I[i][i+j-k-1];   // copy top to right
        O[i][i+j-k-1]=temp;            // copy temp(left) to top
    }
}// end of rotate

int main()
{
    int I[10][10],O[10][10],i,j,N;
    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
            scanf("%d",&I[i][j]);
    }
    i=0;
    j=N;
    while(j>0)
    {
        rotate(I,O,j,i);  // i is base,  j is size
        j=j-2;
        i++;
    }
    printf("\n\n");
    for(i=0;i<N;i++)
    {
        printf("\n");
        for(j=0;j<N;j++)
            printf("%d ",O[i][j]);
    }
return 0;
}

3 comments:

  1. the problem states it it needs to be done in place.
    it seems to me you are using two matrices?

    ReplyDelete
  2. #include

    using namespace std;

    int a[5][5] = { {0,0,0,0,0},
    {1,1,1,1,1},
    {1,2,3,4,5},
    {2,2,2,2,2},
    {3,3,3,3,3}
    };


    void print()
    {
    for(int i = 0;i<5; ++i) {
    for(int j = 0;j<5; ++j)
    cout << a[i][j] << " ";

    cout<<endl;
    }
    cout<<endl;
    }


    void flip() {
    for(int i = 0; i<=2; ++i) {
    for(int j = i;j<4-i; ++j) {
    int tmp = a[i][j];
    a[i][j] = a[j][4-i];
    a[j][4-i] = a[4-i][4-j];
    a[4-i][4-j] = a[4 -j][i];
    a[4-j][i] = tmp;
    }
    }
    }

    int main()
    {
    print();

    flip();


    print();

    flip();


    print();


    return 0;
    }

    ReplyDelete
  3. flip has 2 important points
    1. calculating the indices for 4 nodes from left, right, bott, top sizdes that are going to be switched each time.
    2. for loops stop conditions. basically what happens after first run (i=0, j=0...4), we switch all the side cells. so next time we need to skip all outer cells and go further in.


    Take a look, run an example, try to see how it works.

    ReplyDelete