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

#define min(x,y) ((x) < (y) ? (x) : (y))

// Allocating 2D array
int **Allocate2DArray(int row, int col)
{
	int **matrix, i;

	matrix = (int **)malloc(row * sizeof(int *));
	// Insert code for necessary checking for memory availability
	for (i = 0; i < row; i++) {
		matrix[i] = (int *)malloc(col * sizeof(int));
		// Insert code for necessary checking for memory availability
	}

	return matrix;
}

//Printing 2D array
void Print2DArray(int **M, int r, int c)
{
	int i, j;

	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++)
			printf("%2d ", M[i][j]);
		printf("\n");
	}
}

// Initialize the matrix
void Init2DArray(int **M, int r, int c)
{
	int i, j, val;

	val = 1;
	for (i = 0; i < r; i++)
		for (j = 0; j < c; j++)
			M[i][j] = val++;
}

// Traversing the matrix 'mat' of order rXc, where i denotes the diagonal number
//i = 0 indicates 1st and last diagonal
//i = 1 indicates 2nd and 2nd last diagonal
void Traverse2DArray(int **mat, int i, int r, int c)
{
	// noe the number of elements in i-th diagonal
	int noe, j, x, y;
    
    // terminating condition
	if (i == (r + c) / 2)
		return;
	// noe depends on the i
	if (i >= min(r, c) - 1)
		noe = min(r, c);
	else
		noe = i + 1;

	if (i % 2 == 0)		//diagonal 0,2,4,... i.e., i is even
	{
		// set the starting index of diagonal to be printed depending upon 
		// orientation
		if (i < r) {
			x = i;
			y = 0;
		} else {
			x = r - 1;
			y = i - (r - 1);
		}
		// print the noe elements of diagonal
		for (j = 0; j < noe; j++) {
			printf("%2d ", mat[x][y]);
			x = x - 1;
			y = y + 1;
		}
        
        // guarding multiple printing of middle diagonal
		if (i == (r + c - 1) / 2)
			return;
        
        // set the starting index of diagonal to be printed depending upon 
		// orientation
		if (i < c) {
			x = r - 1;
			y = c - 1 - i;
		} else {
			x = r - 1 - (i - (c - 1));
			y = 0;
		}
		// print the noe elements of diagonal
		for (j = 0; j < noe; j++) {
			printf("%2d ", mat[x][y]);
			x = x - 1;
			y = y + 1;
		}
	} else			//diagonal 1,3,5,... i.e., i is odd
	{
		if (i < c) {
			x = 0;
			y = i;
		} else {
			x = i - (c - 1);
			y = c - 1;
		}
		for (j = 0; j < noe; j++) {
			printf("%2d ", mat[x][y]);
			x = x + 1;
			y = y - 1;
		}
        
        // guarding multiple printing of middle diagonal
		if (i == (r + c - 1) / 2)	
			return;

		if (i < r) {
			x = r - 1 - i;
			y = c - 1;
		} else {
			x = 0;
			y = c - 1 - (i - r + 1);
		}
		for (j = 0; j < noe; j++) {
			printf("%2d ", mat[x][y]);
			x = x + 1;
			y = y - 1;
		}
	}
	printf("\n");
	// Recurse through next diagonal
	Traverse2DArray(mat, i + 1, r, c);
}

int main()
{
	int row, col, **M;

	printf("Enter the dimension (mXn) :");
	scanf("%d %d", &row, &col);

	M = Allocate2DArray(row, col);
	Init2DArray(M, row, col);
	printf("------------------------------------------\n");
	Print2DArray(M, row, col);
	printf("------------------------------------------\n");
	Traverse2DArray(M, 0, row, col);
	printf("------------------------------------------\n");

	return 0;
}