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.
1
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