Spiral Walk / Boyan Mihaylov

We have a square matrix (NxN) of integers. Having given a starting corner point and a direction, we want to walk all the elements from this matrix on a spiral way. I found this problem accidentally and it vexed me. That’s why I decided to create a simple algorithm.

We are going to create a class called SpiralWalk. It provides a method called WalkIt which does all the job. This methods has three arguments: starting row & col index (zero-based) and a direction. Remember, that the point must be a corner point. Every NxN array has four corner points: (0, 0), (0, N-1), (N-1, 0), (N-1, N-1).

public void WalkIt(int startRow, int startCol, Direction direction)

1	public void WalkIt(int startRow, int startCol, Direction direction)

Now, we are going to declare some auxiliary variables.

int r, c;
int rowsLen, colsLen;
int sign;
Direction changeSign;

int r, c;

int rowsLen, colsLen;

int sign;

Direction changeSign;

r : current row index
c: current column index
rowsLen: how many rows to walk, when walking vertically
colsLen: how many columns to walk, when walking horizontally
sign: +1 or -1; it is used to determine when we increase and when decrease row or column index
changeSign: determines when to change the sign (when we walk vertically or horizontally)

REMARK: Direction is an enumeration with two values: Horizontal and Vertical.

This picture below shows how we determine the initial values of sign and changeSign. It shows all eight possible variants (4 corner points * 2 directions). The bold lines indicates that when we are walking on this direction (vertical or horizontal) we should change the sign. The green signs shows the sign and the blue ones – whether we should increase or decrease the corresponding index.

r = startRow;
c = startCol;
rowsLen = colsLen = this.matrix.GetLength(0);

if (direction == Direction.Vertical)
{
	sign = (startCol == 0) ? -1 : 1;
	r += (startRow == 0) ? -1 : 1;
	changeSign = (startRow == startCol) ? Direction.Vertical : Direction.Horizontal;
}
else
{
	sign = (startRow == 0) ? -1 : 1;
	c += (startCol == 0) ? -1 : 1;
	changeSign = (startRow == startCol) ? Direction.Horizontal : Direction.Vertical;
}

r = startRow;

c = startCol;

rowsLen = colsLen = this.matrix.GetLength(0);

if (direction == Direction.Vertical)

{

sign = (startCol == 0) ? -1 : 1;

r += (startRow == 0) ? -1 : 1;

changeSign = (startRow == startCol) ? Direction.Vertical : Direction.Horizontal;

}

else

{

sign = (startRow == 0) ? -1 : 1;

c += (startCol == 0) ? -1 : 1;

changeSign = (startRow == startCol) ? Direction.Horizontal : Direction.Vertical;

}

Now we can start walking! We perform next steps while we say break! First, we check our direction to changeSign to determine whether we have to change the sign.

if (changeSign == direction) sign *= -1;

1	if (changeSign == direction) sign *= -1;

Then we check what is our direction:

if (direction == Direction.Horizontal)
{
	for (int j = 0; j &amp;amp;lt; colsLen; j++)
	{
		c += sign * 1;
		Console.WriteLine("= {0} =", this.matrix[r, c]);
	}

	rowsLen--;
	direction = Direction.Vertical;
}

if (direction == Direction.Horizontal)

{

for (int j = 0; j &amp;lt; colsLen; j++)

{

c += sign * 1;

Console.WriteLine("= {0} =", this.matrix[r, c]);

}

rowsLen--;

direction = Direction.Vertical;

}

We are walking horizontally. We have to walk exactly colsLen elements with row index r. After that we decrease rowsLen, because we have walked a row now and next time, when we go vertically, we should walk less rows. In the end we just change the direction, of course. When we are walking vertically, everything is analogous. We stop walking when we have nothing to walk more – when rowsLen = colsLen = 0.

if (colsLen == 0 &amp;&amp; rowsLen == 0) break;

1	if (colsLen == 0 && rowsLen == 0) break;

[ Source Code ]