/* order.c
Demonstrate traversal orders on a grid.
by: Steven Skiena
begun: July 14, 2002
*/
/*
Copyright 2003 by Steven S. Skiena; all rights reserved.
Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.
This program appears in my book:
"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.
See our website www.programming-challenges.com for additional information.
This book can be ordered from Amazon.com at
http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/
*/
#include "geometry.h"
row_major(int n, int m)
{
int i,j; /* counters */
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
process(i,j);
}
column_major(int n, int m)
{
int i,j; /* counters */
for (j=1; j<=m; j++)
for (i=1; i<=n; i++)
process(i,j);
}
snake_order(int n, int m)
{
int i,j; /* counters */
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
process(i, j + (m+1-2*j) * ((i+1) % 2));
}
diagonal_order(int n, int m)
{
int d,j; /* diagonal and point counters */
int pcount; /* points on diagonal */
int height; /* row of lowest point */
for (d=1; d<=(m+n-1); d++) {
height = 1 + max(0,d-m);
pcount = min(d, (n-height+1));
for (j=0; j