volatile keyword in C / C++
June 12, 2012Turn off the rightmost bit of an integer
June 12, 2012Traversing a matrix in spiral order
Given a Matrix, write a function that will print the elements in spiral order. For example, if the Matrix is as below:
Then the output should be:
1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
Which is the spiral order of given matrix:
Solution:
The given matrix is below:
In a single loop we will print one complete circle of elements. Hence we will have 4 loops inside a bigger loop to print the
1. Top Row from Left to Right
2. Last Column from Top to bottom
3. Last Row from Right to Left
4. First Column Bottom to Top
So first pass (of outer loop, which has the above 4 loops) the elements will get printed as below:
In the next loop we will print the inner circle
And so on..
Code:
void spiralTraversal(int **a, int n)
{
int rs=0, cs=0; // RowStart and Column Start
int re=n-1, ce=n-1; // RowEnd & columnEnd
while(rs<=re && cs<=ce)
{
int i=rs, j=cs;
for(j=cs; j<=ce; j++)
cout<<" "<<a[i][j];
for(i=rs+1, j--; i<=re; i++)
cout<<" "<<a[i][j];
for(j=ce-1, i--; j>=cs; j--)
cout<<" "<<a[i][j];
for(i=re-1, j++; i>=rs+1; i--)
cout<<" "<<a[i][j];
rs++; cs++; re--; ce--;
}
}
8 Comments
can i please see the code?
My bad.. messed it up during copy-pasting the code from computer to website.. thanks for pointing it out.
i think this is doing something different. You very first for loop is going down on the left instead of going right at the top. IOW, I don’t think you should be fixing i and incrementing j.
The main for loop has 4 loops.. the first inner loop will traverse the top row (left to right), second the last column (Top to Down), 3rd will traverse the last row (Right to Left) and final will traverse the first column (Bottom-Up)..
Once the first pass is over (two top/bottom rows and left/right columns are printed).. then the moves on to print the inner matrix.. the start point will be (1,1) hence 2nd row from top will be printed, similarly the 2nd last column will be printed followed by 2nd last row and 2nd column..
And so on..
This will not work for cases where row and column sizes are different and specially in cases where rowstart equals rowend and columnstart equals columnend. in those cases there will be duplicacy of the results printed.
working code :
void traverseMatrixSpirally(int ** a, int numOfRows , int numOfCols).
{
int cs = 0;.
int rs = 0;.
int ce = numOfCols-1;.
int re = numOfRows-1;.
int i, j;
while(rs<= re && cs <= ce).
{
for (i = rs, j = cs ; j<= ce; j++).
Console::Write(" " + a[i][j]);.
if(rs==re)
return;
for(j–, i=rs+1;i<=re;i++)
Console::Write(" " + a[i][j]);.
if(cs==ce)
return;
for(i–, j=ce-1; j>=cs; j–).
Console::Write(" " + a[i][j]);.
for(j++, i=re-1;i>=rs+1;i–)
Console::Write(" " + a[i][j]);.
cs++; rs++; ce–; re–;.
}
}
This will not work for cases where row and column sizes are different and specially in cases where rowstart equals rowend and columnstart equals columnend. in those cases there will be duplicacy of the results printed.
working code :
void traverseMatrixSpirally(int ** a, int numOfRows , int numOfCols).
{
int cs = 0;.
int rs = 0;.
int ce = numOfCols-1;.
int re = numOfRows-1;.
int i, j;
while(rs<= re && cs <= ce).
{
for (i = rs, j = cs ; j<= ce; j++).
Console::Write(" " + a[i][j]);.
if(rs==re)
return;
for(j–, i=rs+1;i=cs; j–).
Console::Write(” ” + a[i][j]);.
for(j++, i=re-1;i>=rs+1;i–)
Console::Write(” ” + a[i][j]);.
cs++; rs++; ce–; re–;.
}
}
but this code works only for square matrix. can you give a more generalized code for any matrix size.
does anybody have code on FREE PASCAL???