Traversing an array spirally

[Praveen]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1 2 3 4
5 6 7 8
9 10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Please help

 

[Chris Thomasson]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1 2 3 4
5 6 7 8
9 10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Is this homework?

 

[Bartc]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1 2 3 4
5 6 7 8
9 10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Please help

Interesting exercise. But not really specific to C except array bounds have
to start at 0.

This is my effort. Probably some clever logic needed but I found it easier
to use a map of 1s and 0s to indicate which array elements have been
visited.

Ints m and n have the array dims hardcoded. Dynamic bounds are a little more
involved.

BTW I'm new to C so if this is homework... don't rely on this!

Bart


#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int m=8,n=6;
int x[n][m];
int map[n][m];
int i,j,k,c,l,count,total,dir;

k=1;
c=1;
l=1;

/* print array grid */
while (1)
{ printf("%3d",k);
++k;
++c;
if (c>m)
{
printf("\n");
c = 1;
++l;
if (l>n) break;
}
}

printf("\n");

/* Set up map of 1's for each array element */
k = 1;
for (j=0; j<n; ++j)
for (i=0; i<m; ++i)
{
x[j] = k++; /* the grid */
map[j] = 1; /* the map */
};


/* now search clockwise spiral */
i = 0;
j = 0;
dir = 'R'; /* One of 4 directions R D L U */
total = m*n;
count = 0;

while (1)
{/*w1"*/

printf(" %d",x[j]); /* output contents of this grid element */
map[j] = 0; /* mark as visited */
++count;
if (count==total) break;

while (1)
{/*w2*/
switch (dir)
{/*sw*/
case 'R':
if (i<(m-1) && map[j][i+1])
{++i;
goto endwhile; /* C can't use break out of 2 levels */
}
else
dir = 'D';
break;
case 'D':
if (j<(n-1) && map[j+1])
{++j;
goto endwhile;
}
else
dir = 'L';
break;
case 'L':
if (i>0 && map[j][i-1])
{--i;
goto endwhile;
}
else
dir = 'U';
break;
case 'U':
if (j>0 && map[j-1])
{--j;
goto endwhile;
}
else
dir = 'R';
break;
}; /*sw*/
}; /*w2*/
endwhile:;

}; /*w1*/

printf("\n");
}

 

[santosh]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1 2 3 4
5 6 7 8
9 10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Please help

In addition to the other responses I also recommend that you do a search
of Google Groups' archive of comp.lang.c. This is a fairly regular
homework problem and there have been many good answers given over the
years.

 

[yeti]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1 2 3 4
5 6 7 8
9 10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Please help

Hmm I guess this is not s C question, but anyway this is my strategy

strategy 1

1. print first line
2. remove first line
3. take transpose of matrix
4 go to step 1 till matrix is not empty

strategy 2

assuming a function printcircle(mat) that prints boundary circle of a
matrix beginning at first element
i=0,j=0
1. printcircle(&(mat[j]))
2. i++,j++
3. goto step 1 till matrix is not empty

 

[Randy Howard]

In addition to the other responses I also recommend that you do a search
of Google Groups' archive of comp.lang.c. This is a fairly regular
homework problem and there have been many good answers given over the
years.

Yes, by all means, help make sure that he doesn't accidentally learn
anything during this or any other course. We need more college grads
that don't understand the material on their diploma.

 

[Chris Thomasson]

Is this homework?

If it is, go ahead and post your solution before you turn it in. Only then
can we give you some "pointers" to help you out some... Think about it: Do
the work, and ask for some clues on how you can make a possible improvement.
IMHO, that's okay; just don't ask us to do it all for you... That would mean
you did not learn; which is BAD!

Also, ask your professor for tips and tricks; do NOT be afraid/intimidated
to ask for help!!!

 

[Army1987]

I would like to know how to traverse an array spirally?

[snip]
Hmm I guess this is not s C question, but anyway this is my strategy

strategy 1

1. print first line
2. remove first line
3. take transpose of matrix
4 go to step 1 till matrix is not empty

An O(n**4) strategy where the most naive one is O(n**2)?

strategy 2

assuming a function printcircle(mat) that prints boundary circle of a
matrix beginning at first element
i=0,j=0
1. printcircle(&(mat[j]))

How do you implement printcircle?

 

[user923005]

Hi,

I would like to know how to traverse an array spirally?
i.e if I have an array as follows

1   2   3  4
5   6   7  8
9   10 11 12

I want the output to be 1 2 3 4 8 12 11 10 9 5 6 7.

Your question is more appropriate on
In order to solve it, ask yourself how you would solve it with pencil
and paper.
It appears that you would traverse the top and edges and then
increment or decrement the edge as appropriate and then repeat until a
dimension is zero.

Try it symbolically with this matrix that has m rows and n columns:

{col 0} {col 1} {col n-1} {col n}
[A(0,0)] [A(0,1)] ... [A(0,n-1)] [A(0,n)] {row 0}
[A(1,0)] [A(1,1)] ... [A(1,n-1)] [A(1,n)] {row 1}
...
[A(m-1,0)][A(m-1,1)]... [A(m-1,n-1)][A(m-1,n)] {row m-1}
[A(m,0)] [A(m,1)] ... [A(m,n-1)] [A(m,n)] {row m}

Once you figure out how you would do it using two indexes i and j on
paper, do exactly the same thing using C.

 

[yeti]

I would like to know how to traverse an array spirally?

[snip]
Hmm I guess this is not s C question, but anyway this is my strategy

strategy 1

1. print first line
2. remove first line
3. take transpose of matrix
4 go to step 1 till matrix is not empty

An O(n**4) strategy where the most naive one is O(n**2)?> strategy 2

assuming a function printcircle(mat) that prints boundary circle of a
matrix beginning at first element
i=0,j=0
1. printcircle(&(mat[j]))

How do you implement printcircle?

2. i++,j++
3. goto step 1 till matrix is not empty

here is the complete program (not tested)

#include <stdio.h>
#define COLS 6
#define ROWS 6

int array[ROWS][COLS]=
{{1 ,2 ,3 ,4 ,5 ,6 },
{7 ,8 ,9 ,10,11,12},
{13,14,15,16,17,18},
{19,20,21,22,23,24},
{25,26,27,28,29,30},
{31,32,33,34,35,36}
};

void printcircle(int map_ptr[][COLS], int rows, int cols)
{
int j=0;
if(rows<1 || cols <1)
{
return;
}
for(j=0; j<cols; j++)
{
printf("%d->", map_ptr[0][j]);
}

for(j=1; j<rows; j++)
{
printf("%d->", map_ptr[j][cols-1]);
}
for(j=cols-2; j>=0; j--)
{
printf("%d->", map_ptr[rows-1][j]);
}
for(j=rows-2; j>=1; j--)
{
printf("%d->", map_ptr[j][0]);
}

}


int main()
{ int rows=ROWS,cols=COLS,i=0;

while(rows>0&&cols>0)
{
printcircle((int(*)[])&array,rows,cols);
rows-=2;
cols-=2;
i++;
}
getchar();
return 0;
}