Sunday, August 18, 2013

Matrix Rotation by 90 Degree Clockwise direction

// Matrix rotation by 90 degree clockwise direction...for N*N matrix.

solution 1:- No extra space.(with extra space see below solution).
#include <stdio.h>
#include <string.h>
#include <math.h>
#define N 4   // for row and column (square matrix).
void Display(int arr[N][N])
{
int i=0,j=0;
for(i=0;i<N;i++)
{ for(j=0;j<N;j++)
  printf("%d ",arr[i][j]);
printf("\n");
}
}
//Rotation goes here
void Rotate(int arr[N][N])
{
int i,j,k,p,temp;  

for(i=0;i<sqrt(N);i++)
{
  k=N-1-i;p=N-1-i;
  for(j=i;j<N-i-1;j++)
  {
      temp=arr[i][j];
      arr[i][j]=arr[k][i];
      arr[k][i]=arr[p][k];
      arr[p][k]=arr[j][p];
      arr[j][p]=temp;
     k--;
  }
}
}
main()
{
    int arr[N][N];
    int i=0,j=0;
    for(i=0;i<N;i++)
     for(j=0;j<N;j++)
       scanf("%d",&arr[i][j]);
      Rotate(arr);
       Display(arr);
      return 0;
}

solution2:- with O(N) extra space

#include <stdio.h>
#include <string.h>
#define N 3
void Display(int arr[N][N])
{
int i=0,j=0;
for(i=0;i<N;i++)
{ for(j=0;j<N;j++)
  printf("%d ",arr[i][j]);
printf("\n");
}
}
//Rotation goes here
void Rotate(int arr[N][N])
{
int i,j,k,p,temp;  
int T[N];
for(i=0;i<2;i++)
{
    for(j=i;j<N-i;j++)
    {
    T[j]=arr[i][j];  
    }
    j--;
    for(k=i;k<N-i;k++)
    {
        temp=arr[k][j];
        arr[k][j]=T[k];
        T[k]=temp;
    }
    k=k--;
    p=i+1;
    for(k--;k>=i;k--)
    {
        temp=arr[j][k];
        arr[j][k]=T[p];
        T[p++]=temp;
    }
    p=i+1;//
    k++;
    for(--j;j>=i;j--)
    {
        temp=arr[j][k];
   
       arr[j][k]=T[p];
        T[p++]=temp;
    }
    j=i;p=i+1;
    for(k=p;k<N-p;k++)
    arr[j][k]=T[k];
}
}
main()
{
    int arr[N][N];
    int i=0,j=0;
    for(i=0;i<N;i++)
     for(j=0;j<N;j++)
       scanf("%d",&arr[i][j]);
      Rotate(arr);
       Display(arr);
      return 0;
}

No comments:

Post a Comment