Monday, 3 August 2015

TCS codevite 2014 question with solution Matrix Rotations

Problem : Matrix Rotations

You are given a square matrix of dimension N. Let this matrix be called A. Your task is to rotate A in clockwise direction byS degrees, where S is angle of rotation. On the matrix, there will be 3 types of operations viz. 
  1. Rotation
    Rotate the matrix A by angle S, presented as input in form of A S 
  2. Querying
    Query the element at row K and column L, presented as input in form of Q K L
  3. Updation
    Update the element at row X and column Y with value Z,  presented as input in form of U X Y Z
Print the output of individual operations as depicted in Output Specification


Input Format:

Input will consist of three parts, viz.
1. Size of the matrix (N)
2. The matrix itself (A = N * N)
3. Various operations on the matrix, one operation on each line. (Beginning either with A, Q or U)

-1 will represent end of input.
Note:
  • Angle of rotation will always be multiples of 90 degrees only.
  • All Update operations happen only on the initial matrix. After update all the previous rotations have to be applied on the updated matrix

Output Format:

For each Query operation print the element present at K-L location of the matrix in its current state.

Constraints:

1<=N<=1000
1<=Aij<=1000
0<=S<=160000
1<=K, L<=N
1<=Q<=100000


Sample Input and Output


SNo.InputOutput
1
2
1 2
3 4
A 90
Q 1 1
Q 1 2
A 90
Q 1 1
U 1 1 6
Q 2 2
-1

3
1
4
6


Solution:


#include<iostream>
using namespace std;
int n,mat[1000][1000],initial[1000][1000];
int temp[1000][1000];
//void print();
void transpose();
void rotate(int);
int main(){
    int x,y,z;
    int total=0;
char c;
cin>>n;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        cin>>mat[i][j];
        initial[i][j]=mat[i][j];
}
}
while(true){
    cin>>c;
    if(c=='A'){
        cin>>x;
        rotate(x);
        total+=x;
    }
    else if(c=='Q'){
        cin>>x>>y;
        cout<<mat[x-1][y-1]<<endl;
    }
    else if(c=='U'){
            cin>>x>>y>>z;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                mat[i][j]=initial[i][j];
        }
        mat[x-1][y-1]=z;
        rotate(total);
        //print();
    }
    else
        break;
}
return 0;
}

void transpose(){
 for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        temp[j][n-i-1]=mat[i][j];
    }
 }
 for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        mat[i][j]=temp[i][j];
    }
 }
}
void rotate(int x){
int t=x/90;
t=t%4;
while(t--){
    transpose();
       // print();
}
}/*
void print(){
    cout<<"printing matrix\n";
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        cout<<mat[i][j]<<" ";
    }
    cout<<endl;
}
}*/

No comments:

Post a Comment