// 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;
}
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