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.
Please help me out with it's code
Answers
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