Traverse a Sparse matrix in reverse spiral order. The Sparse matrix is represented in the form of a triplet [rowindex,columnindex,value] following row-major order. The starting point for traversal, i.e. the row index and the column index is given as an input. The sequence of directions to be followed from the given starting point is Down (1), Right (2), Up (3), and then Left (4).
The output should be in the form of a quadruplet with rows arranged in the required order of traversal. The first three columns of this quadruplet are similar to those as given in the input triplet. The last column includes the direction information which is followed when the corresponding element is traversed. The allowed values in the last column are:
1: If element is traversed while moving Down.
2: If element is traversed while moving Right.
3: If element is traversed while moving Up.
4: If element is traversed while moving Left.
Input:
Line 1 contains three space separated integers, P, Q, and N, where P is the first and Q is the second dimension of a Sparse matrix. N is the total number of non-zero entries in the Sparse matrix.
Each of the following N lines contains three space separated integers representing a single row of the triplet, i.e. rowindex, columnindex, and value.
Last line contains two space separated integers, I and J, respectively giving the starting row and column indices for reverse spiral traversal of the Sparse matrix.
Output:
Each row of the quadruplet is contained in N separate lines. Each line in the output has four space separated integers in the format as is described above.
Constraints
All integers range in between 1 and 1000.
Sample Input:
4 4 5
0 0 8
1 1 6
1 2 5
2 3 9
3 2 7
1 1
Sample Output:
1 1 6 1
1 2 5 3
0 0 8 4
3 2 7 2
2 3 9 3
EXPLANATION:
We have to start from [1][1] and direction to be followed is Down (1), so the first entry should be 1 1 6 1. Next entries traversed in the reverse spiral order are at indices [2][1] and [2][2], but corresponding triplet entries are missing so no output is generated. Then 5 comes at [1][2] while moving Up (3). Triplet entries for [0][2] and [0][1] are again missing. Then at [0][0] element 8 comes while moving Left (4). Again missing triplet entries for [1][0], [2][0], [3][0], and [3][1] generate no output. Element 7 is visited when moving Right (2) at index [3][2]. Triplet entry for [3][3] is missing. Lastly we found element 9 at [2][3] when moving Up (3). Rest of the triplet entries are missing, i.e. [1][3] and [0][3]. This completes the reverse spiral traversal.
Answers
Answer:
Explanation:Q1: A string of characters including only alphabets (lowercase letters) is provided as an input. The first task is to compute the frequency of each character appearing in the string. In the output, the characters have to be arranged in the same order as they appear in the input string. • Then characters have to be rearranged, such that all the characters having a specific frequency, say x, come together. Let the frequency of a character, lying in between the two characters having same frequency x, be y. The steps to be followed for getting the desired arrangement are as follows: • Ify > x, then shift the character at the end. • If y< x, then shift the character at the beginning. Input: • Line 1 contains the string of characters without spaces. • Line 2 contains an integer N. • Line 3 contains N integers separated by space, N1 N2 ... NN. These are the specific frequency values whose corresponding characters should come together. Output: • Line 1 has characters and their frequency as computed originally. Each output value is separated using a space.
Answer:
#include <iostream>
using namespace std;
int main(){
int r,c,n;
cin>>r>>c>>n;
int a[r][c];
int b[r][c];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
a[i][j]=0;
b[i][j]=0;
}
}
for(int k=0;k<n;k++){
int i,j;
cin>>i>>j;
cin>>a[i][j];
}
int si,sj;
cin>>si>>sj;
int d=0;
int i,j;
i=si;j=sj;
int co=0;
while(true){
co++;
if(co>2){
break;
}
// first time we have to move down
if(b[i][j]==0 && i==si && j==sj && a[i][j]!=0){
cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<1<<endl;
b[i][j]=1;
}
if(d==0){
if(i<r-1 && b[i+1][j]!=1){
i++;
if(a[i][j]!=0){
cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<d+1<<endl;
}
b[i][j]=1;
co=0;
}
d++;
d%=4;
}
if(d==1){
if(j<c-1 && b[i][j+1]!=1){
j++;
if(a[i][j]!=0){
cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<d+1<<endl;
}
co=0;
b[i][j]=1;
}
d++;
d%=4;
}
if(d==2){
if(i>0 && b[i-1][j]!=1){
i--;
if(a[i][j]!=0){
cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<d+1<<endl;
}
co=0;
b[i][j]=1;
}
d++;
d%=4;
}
if(d==3){
if(j>0 && b[i][j-1]!=1){
j--;
if(a[i][j]!=0){
cout<<i<<" "<<j<<" "<<a[i][j]<<" "<<d+1<<endl;
}
b[i][j]=1;
co=0;
}
d++;
d%=4;
}
}
}
Explanation:
Just focus on moving Down Right Up Left if location is available
array b stores the visited locations
si sj are starting indexes
co is counter
d is direction