/*As an exercise, rewrite this code using and passing structures 
 to represent the array indices*/


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

int no_of_elements = 1;

int ** Allocate2DMatrix(int row, int col)
{
  int k, **S; 
  S=(int **)calloc(row,sizeof(int *));  
  if(S==NULL)  {  
                 printf("\n No space \n"); 
                 exit(0);  
               }  
  for(k=0; k<row; k++)  
  {  
    S[k]=(int *)calloc(col,sizeof(int));   
    if(S[k]==NULL){ 
                    printf("\n No space \n"); 
                    exit(0);  
                  }  
  }  
  return S; 
}

void Fill2DMatrix(int **S, int row, int col)
{
  int i,j,k=1;
  for(i=0;i<row;i++)
   {
    for(j=0;j<col;j++)
     S[i][j]= k, k++;
   }
  return; 
}

void Print2DMatrix(int **S, int row, int col)
{
  int i,j;
  for(i=0;i<row;i++)
   {
    for(j=0;j<col;j++)
       printf("\t %d",S[i][j]);
    printf("\n");
   }   
  return; 
}

void Diagonal_Print(int **S, int direction, int row_start, int col_start, 
                    int row_end, int col_end)
/* The direction variable encodes the direction of printing, 0 (1) stands 
   for printing from left bottom (top right) to top right (left bottom).
   row_start and col_start has the start row and column values of the 
   left bottom indices, and row_end and col_end has the end row and 
   column values of the right top indices.
*/
{
    int i, j; 
    if(direction == 0)
    {
      for(i=row_start, j= col_start;i>=row_end && j<=col_end;i--, j++)
        printf("\t %d",S[i][j]);

      printf("\n");
    }
    else
    {
      for(i=row_end, j= col_end;i<=row_start && j>=col_start;i++, j--)
        printf("\t %d",S[i][j]);

        printf("\n");
    }
 return;
}

void PrintDiag(int **S,int row, int col,
               int print_from_left, 
               int print_diag_upper,int print_diag_lower, 
               int diag_start_row_top,int diag_start_col_top, int diag_end_row_top, 
               int diag_end_col_top, 
               int diag_start_row_bottom, int diag_start_col_bottom, int diag_end_row_bottom, 
               int diag_end_col_bottom, 
               int *printed_till_now, int no_of_elements)
{
 
  /* Logic starts from here */
  if(*printed_till_now>=no_of_elements) /* stopping criterion of the recursion */
    return;
  
  if(print_from_left == 0) /* dealing with leftmost diagonals*/
  {
    Diagonal_Print(S,print_diag_upper, diag_start_row_top,diag_start_col_top, diag_end_row_top, 
                   diag_end_col_top); /*Prints the current diagonal of left */

    print_from_left = 1; /* Toggle the diagonal */

    *printed_till_now = *printed_till_now + abs(diag_start_row_top - diag_end_row_top)+1;
    /* Updates the number of elements printed in the current diagonal*/


    /* Toggle the direction for the next diagonal */
    if(print_diag_upper ==1) print_diag_upper = 0; 
    else print_diag_upper = 1;
 
    /* Set the values of the new row and column indices 
       Do this carefully. */
    if(diag_start_row_top <= row-2 &&  diag_start_col_top== 0)
      diag_start_row_top += 1;   
    else if(diag_start_row_top == row-1)
      diag_start_col_top++; 

    if(diag_end_row_top == 0 &&  diag_end_col_top <= col-2)
      diag_end_col_top += 1;   
    else if(diag_end_col_top == col-1)
      diag_end_row_top++; 
    
  }
  else /* dealing with rightmost diagonals*/
  { 
    Diagonal_Print(S,print_diag_lower, diag_start_row_bottom, diag_start_col_bottom, 
          diag_end_row_bottom, diag_end_col_bottom); /*Prints the current diagonal of right */

    print_from_left = 0; /* Toggle the diagonal */

    *printed_till_now = *printed_till_now + abs(diag_start_row_bottom - diag_end_row_bottom)+1;
    /* Updates the number of elements printed in the current diagonal*/

    /* Toggle the direction for the next diagonal */
    if(print_diag_lower ==1) print_diag_lower = 0; 
    else print_diag_lower = 1; 

    /* Set the values of the new row and column indices 
       Do this carefully. */
    if(diag_start_col_bottom >= 1 &&  diag_start_row_bottom== row-1)
      diag_start_col_bottom -= 1;   
    else if(diag_start_col_bottom == 0)
      diag_start_row_bottom--; 

    if(diag_end_col_bottom == col-1 &&  diag_end_row_bottom >= 1)
      diag_end_row_bottom -= 1;   
    else if(diag_end_row_bottom == 0)
      diag_end_col_bottom--; 

  }
  
  /* Make the next recursive call */
  PrintDiag(S,row, col, print_from_left,print_diag_upper,print_diag_lower,
            diag_start_row_top,diag_start_col_top, diag_end_row_top, diag_end_col_top, 
         diag_start_row_bottom, diag_start_col_bottom, diag_end_row_bottom, diag_end_col_bottom,
         printed_till_now,no_of_elements); 
  return;
  
}

int main(void)
{
  int **matrix, row, col;
  
  int print_from_left; 
  /* print_from_left==0 (==1) indicates printing diagonals from left (right) of the matrix*/
  int print_diag_upper, print_diag_lower; 
  /* These variables encode the direction of printing; 0 indicates printing 
     from bottom-left to top-right and 1 indicates the opposite */
  int diag_start_row_top, diag_start_col_top, diag_end_row_top, diag_end_col_top;
  /* These variables store the end indices of the diagonal that is being printed 
     from the left */
  int diag_start_row_bottom, diag_start_col_bottom, diag_end_row_bottom, diag_end_col_bottom;
  /* These variables store the end indices of the diagonal that is being printed 
     from the right */ 
  int printed_till_now, no_of_elements;
  /* These variables are needed for checking the end condition of recursion.*/
  
  
  printf("Row = ");   scanf("%d",&row);
  printf("Column = ");scanf("%d",&col);
  
  no_of_elements = row*col; 
  printed_till_now = 0; 

  matrix = Allocate2DMatrix(row,col);
  Fill2DMatrix(matrix,row,col);
  printf("\n The original matrix ::> \n ");
  Print2DMatrix(matrix,row,col);
  printf("\n");

  /* Check for boundary conditions row==1 and col==1*/
  if(row==1 && col ==1) {Print2DMatrix(matrix,row,col);exit(0);}
  
  /* Set the initial conditions */
  print_from_left = 0, print_diag_upper = 0, print_diag_lower = 0;

  diag_start_row_top = 0, diag_start_col_top = 0;  
  diag_end_row_top = 0, diag_end_col_top = 0; 

  diag_start_row_bottom = row-1, diag_start_col_bottom=col-1; 
  diag_end_row_bottom = row-1, diag_end_col_bottom = col-1;
  /* Finishing setting the initial conditions */
  
  printf("\n The weird way to print the matrix ::> \n ");
  /* The first call to the recursive function */
  PrintDiag(matrix,row, col, print_from_left,print_diag_upper,print_diag_lower,
            diag_start_row_top,diag_start_col_top, diag_end_row_top, diag_end_col_top, 
         diag_start_row_bottom, diag_start_col_bottom, diag_end_row_bottom, diag_end_col_bottom,
         &printed_till_now,no_of_elements);
  printf("\n \n");
  return 0;
}