/*****************************************************************************************/
/* WN Sahpe                                                   - 1 Augest     2008        */
/* File Name: WN.c 						                       	 */
/* Written By Mohammed Thaher                                                  		 */
/* Student Number :  52677556.                                  		         */
/* Supervisor : Dr.Tadao Takaoka                                                         */
/*****************************************************************************************/ 

#include <stdio.h>  
#include <stdlib.h>
#include <time.h>
#define rows 4 
#define cols 8
int aw[rows+1][rows+1][cols+1]; // max W gain 
int an[rows+1][rows+1][cols+1]; // max N gain 
int bw[rows+1][rows+1][cols+1]; 
int bn[rows+1][rows+1][cols+1];
int sw[rows+1][rows+1][cols+1]; 
int pref[rows+1][cols+1];

int fw(int i, int j, int k); 
int gn(int i, int j, int k); 
int fn(int i, int j, int k); 

int a[rows+1][cols+1]; // original matrix 
int region[4][8];
int ii,jj,kk; 

int main(void) { FILE *fp,*fp1; 	
  int i,m,n,l,trows, tcols,k=0,t,j,x, sum; 
  int wn, maxwn=-10000, im=0, jm=0, km=0;

  fp=fopen("4x8T.txt", "r"); 
  if (fp==NULL) { printf("Cant open the file"); 
    exit(EXIT_FAILURE); 
  } 
  fscanf(fp,"%d",&trows);fscanf(fp,"%d",&tcols); 

  for(m=1;m<=rows;m++){ 
	for(n=1;n<=cols;n++){ fscanf(fp, "%d", &i); a[m][n]=i; 
	}; 
  }; 
  fclose(fp); 
  fp1 = fopen("output.txt","ab"); 
  if (fp1==NULL){	printf ("cant open the file");exit(EXIT_FAILURE); 
  } 

	
/******************************* time start *******************************/
       
    clock_t start_clock=clock(); 
   //cut and paste this line where ever you want to start counting clock

/*************************************************************************/ 

	original_a(jm, km); 
	printf("\n\n");

/*************************** New addition prefix sum *********************/ 
	// j 
	{int i, j, k; 				//         k
	for(i=1; i<=rows; i++) 			//   |    | |    | 
          for(j=1; j<=cols; j++){ 	        // i |    | |    | 
	    pref[0][j]=0; 	        	//   |    | |    | 
	    for(k=1; k<=i; k++)                 // j |    | |    |
		pref[k][j]=pref[k-1][j]+a[k][j]; 
	    } 
	} 
      

/**********************************************************************/ 
	//W Calculation 
	{int i,j,k;
	for(k=1;k<=cols;k++){      // <  ---> <=
          for(t=0; t<=rows-1;t++){ 
	    for(i=1; i<=rows-t; i++){ 
		j=i+t; fw(i,j,k); 
	    }; 
	  }; 
	}; 
	}

	//N Calculation 
	{int i,j,k;
	for(k=1;k<=cols;k++){      // <  ---> <=
		for(t=rows-1; t>=0;t--){ 
			for(i=1; i<=rows-t; i++){ 
				j=i+t; if(j<=rows) gn(i,j,k); 
				}; 
			}; 
		}; 
	}
	//WN Calculation 
	{int i, j, k;
 	for(k=1;k<=cols;k++){ 
          for(t=0; t<=rows-1;t++){ 
	    for(i=1; i<=rows-t; i++){ 
		j=i+t; 
		wn=an[i][j][k]; 
		if (wn>=maxwn){ maxwn = wn; im=i; jm=j; km=k; 
	         		} 
	    }; 
	  }; 
	};
        } 
	printf("MaxWN[%d][%d][%d] = %d \n", im,jm,km,maxwn); 

/***This part is to back track on N shape**********************************************/ 
	kk=km; ii=im; jj=jm; 
    	{ int i; for(i=im;i<=jm;i++)region[i][km]=1;}
 	while((an[im][jm][km]>0)&&(bn[im][jm][km]>0)){ 
      	  if(bn[im][jm][km]==1)km--; else
      	  if(bn[im][jm][km]==2)im--; else
     	  if(bn[im][jm][km]==3)jm++;
   	}
/*******This part is to back track in W shape***********************************/
   	while((km>0)&&(aw[im][jm][km]>0)){
    	  if(bw[im][jm][km]==1)km--; else
    	  if(bw[im][jm][km]==2)im++; else
    	  if(bw[im][jm][km]==3)jm--;
     	{ int i; for(i=im;i<=jm;i++)region[i][km]=1;}
  	}
  	if((aw[im][jm][km]==0)&&(bw[im-1][jm][km]==2)) region[im][km]=0;
   	if((aw[im][jm][km]==0)&&(bw[im][jm+1][km]==3)) region[jm][km]=0;
/************************************************************************/
	
	{int i, j; 
          for(i=1;i<=rows; i++){ 
       	    printf("%2d ", i); 
	     for(j=1;j<=cols;j++)printf("%3d ", region[i][j]); printf("\n"); 
          } 
        } 
	fprintf(fp1,"\nMaxWN[%d][%d][%d] =  %d ", im,jm,km,maxwn); 
	
/******************************** end time ********************************/
  	
fprintf(fp1,"\nTime taken = %g",(clock()-start_clock)/(double)CLOCKS_PER_SEC);
 
/***************************************************************************/
fclose(fp1); 
} 

/********************************** end main********************************/ 
  
original_a(int j, int k){ // Output original matrix 
	int ii,jj; 
	  for(ii=1;ii<=rows; ii++){ 
        	 printf("%2d ", ii); 
	   for(jj=1;jj<=cols;jj++)printf("%3d ", a[ii][jj]); printf("\n"); 
	} 
  for(ii=0;ii<=rows+1; ii++){a[ii][0]=999; a[ii][cols+1]=999;} 
  for(jj=0;jj<=cols+1; jj++){a[0][jj]=999; a[rows+1][jj]=999;} 
} 

/******************************** fw **************************************/
int fw(int i, int j, int k){ 
	int f1,f2,f3,sum=0,l; 
	//IF the column number is 0 then return 0 
	if (k<=0){ 
		aw[i][j][k]=0; 
	} 
	if (j<i) { aw[i][j][k]=0; } 
	//initialize fw(1,1,1), fw(2,2,1), fw(3,3,1) etc. 
	if(k==1 && i==j) aw[i][j][k]=a[i][k]; 
	  sum=pref[j][k]-pref[i-1][k]; // New line 
	  f1=aw[i][j][k-1]+sum; 
	  f2=aw[i+1][j][k]+a[i][k]; 
	  f3=aw[i][j-1][k]+a[j][k]; 
	//return the maximum of f1,f2,f3 
	if (f1>=f2 && f1>=f3) { aw[i][j][k]=f1; bw[i][j][k]=1; } 
	else{ 
		if(f2>=f1 && f2>=f3){ aw[i][j][k]=f2; bw[i][j][k]=2; } 
		else { aw[i][j][k]=f3; bw[i][j][k]=3; } 
	} 
} 

/******************************* gn **************************************/
int gn(int i, int j, int k){ 
	int g1,g2,g3,g4,sum=0,l; 
	//If the column number is 0 then return 0 
	if (k<=0){ an[i][j][k]=0; } 
	if (j<i) { an[i][j][k]=0; } 
	//initialize gn(1,1,1), gn(2,2,1), gn(3,3,1) etc. 
	if(k==1 && i==j) an[i][j][k]=a[i][k]; 
	sum=pref[j][k]-pref[i-1][k]; // New line 
        if(k==1){an[i][j][k]=sum;}
        else { 
	g1=an[i][j][k-1]+sum; 
	g2=an[i-1][j][k]-a[i-1][k]; 
	g3=an[i][j+1][k]-a[j+1][k]; 
        g4=aw[i][j][k-1]+sum;   // If g4 is chosen, (i,j,k) is anchor pillar
	//return the maximum of g1,g2,g3,g4 
	if((g1>=g2)&&(g1>=g3)&&(g1>=g4)){ an[i][j][k]=g1; bn[i][j][k]=1; } 
	if((g2>=g1)&&(g2>=g3)&&(g2>=g4)){ an[i][j][k]=g2; bn[i][j][k]=2; } 
	if((g3>=g1)&&(g3>=g2)&&(g3>=g4)){ an[i][j][k]=g3; bn[i][j][k]=3; } 
	if((g4>=g1)&&(g4>=g2)&&(g4>=g3)) {an[i][j][k]=g4; bn[i][j][k]-0; } 
                                         // bn=0 means (i,j,k) is anchor
       } 
}