/*****************************************************************************************/
/* WN Sahpe                                                   - 24th July     2008       */
/* File Name: kconvex.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 pref[rows+1][cols+1]; 

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

int a[rows+1][cols+1]; // original matrix 
int region[100][100]; 
int ri, rj, rk; 
int ii,jj,kk; 
int KKK=1;
FILE *fp,*fp1; 
int main(void) 
{ 
	
	
	int i,m,n,l,trows, tcols,t,j,x; 
	int wn,maxwn,im,jm,km,k,sum;


	fp=fopen("4x8.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); 

	for(KKK=1; KKK<=9; KKK++){

	wn=0; maxwn=-1000000; im=0; jm=0; km=0; k=0;sum=0;
	t=0;j=0;x=0,ri=0;rj=0;rk=0,ii=0,jj=0,kk=0;

	for(i=1;i<=rows; i++)	
		  for(j=1;j<=cols;j++){
			  region[i][j]=0;
			  pref[i][j]=0;
		  };

	for (m=1;m<rows;m++){
		for (n=1;n<rows;n++){
			for (l=0;l<cols;l++){
				aw[m][n][l]=0;an[m][n][l]=0;bw[m][n][l]=0;bn[m][n][l]=0;
			};
		};
	};
	
	for (m=1;m<rows;m++)
		for (n=1;n<rows;n++){
			aw[m][n][0]=0;
		};

	fp1 = fopen("output.xls","ab"); 
	if (fp1==NULL)
	{	printf ("cant open the file"); 
		exit(EXIT_FAILURE); 
	} 

	/********** New addition prefix sum *********************/ 
	// j 
	{int i, j, k; // | | | | 
	for(i=1; i<=rows; i++) // | k| | | 
		for(j=1; j<=cols; j++){ // i| | | | 
			pref[0][j]=0; // | | | | 
			for(k=1; k<=i; k++) 
				pref[k][j]=pref[k-1][j]+a[k][j]; 
		} 
	} 
	/********************************************************/ 
	//W Calculation 
	for(k=0;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 
	for(k=cols;k>=1;k--){ 
		for(t=0; t<=rows-1;t++){ 
			for(i=1; i<=rows-t; i++){ 
				j=i+t; fn(i,j,k); 
			}; 
		}; 
	}; 
	//WN Calculation 
	//fprintf(fp1,"\n WN Calculation \n"); 
	for(k=1;k<=cols;k++){ 
		for(t=0; t<=rows-1;t++){ 
			for(i=1; i<=rows-t; i++){ 
				j=i+t; 
				sum=pref[j][k]-pref[i-1][k]; 
				wn=aw[i][j][k]+an[i][j][k]-sum; 
				if (wn>=maxwn){ maxwn = wn; im=i; jm=j; km=k; 
				} 
			}; 
		}; 
	}; 
	printf("\n");
	original_a(jm, km); 
	printf("\nMaxWN[%d][%d][%d] = %d \n", im,jm,km,maxwn); 

	printf("\n\n");

	kk=km; ii=im; jj=jm; 

	
	while(km>0 && aw[im][jm][km]!=0){ // Record position (im,km) and (jm,km) in region and stops the while loop when max w for current region becomes zero
	
		
	region[im][km]=1; 
	region[jm][km]=1; 
		if(bw[im][jm][km]==1)
		{	km--; 
			//region[im][km]=1; 
			//region[jm][km]=1; 
			
		}
		else 
			if(bw[im][jm][km]==2)
			{	im++;
				
				//region[im][km]=1;
				//region[jm][km]=1; 
				
			}
			else 
				if(bw[im][jm][km]==3)
				{	jm--; 
					
					//region[im][km]=1; 
					//region[jm][km]=1; 
					
				}
		
	} 

	region[im][km]=0; // now I put im or jm element of km row as zero and stops the while loop when max w for current region becomes zero

	im=ii; jm=jj; km=kk; 


	while(km<=cols && an[im][jm][km]!=0){ 
			region[im][km]=1; 
	region[jm][km]=1; 
		if(bn[im][jm][km]==1)
		{
			km++;
		} 
		  else 
			  if(bn[im][jm][km]==2)
			  {
				  im++; 
				  
			  }
			  else 
				  if(bn[im][jm][km]==3)
				  {
					  jm--;
						
				  } 
	} 
	region[im][km]=0;// now we put im or jm element of km row as zero

	{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"); 
	} 
	} 
	printf("------------------------------------------------\n");
	fclose(fp1); 
	
int start =0, end=0;
for(i=1;i<=rows; i++)	{
		  for(j=1;j<=cols;j++){
			  if (region[i][j]==1){
				  start=j;
				  
				  break;
			  }  
		  };
		  for(j=cols;j>=1;j--){
			  if (region[i][j]==1){
				  end=j;
				  
				  break;
			  }  
		  };
			//printf("start %d \n",start);
			//printf("end %d \n",end);
		  for (j=start; j<=end; j++)
			  a[i][j]=-9999;
		  start=0; end=0;
}

//original_a(jm, km); 

};

} // 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"); 
	} 
} 

int fw(int i, int j, int k){ 
	int f1,f2,f3,sum=0,l,pp; 
	//IF the column number is 0 then return 0 
	if (k<=0){ 

		aw[i][j][k]=0; return;
	} 

	if (j<i)  {aw[i][j][k]=0; return;}
	//} 
	//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; } 
	}
	fprintf(fp1,"aw[%d][%d][%d] = %d \t bw[%d][%d][%d]=%d\n",i,j,k,aw[i][j][k],i,j,k,bw[i][j][k]);
} 
int fn(int i, int j, int k){ 
	int f1,f2,f3,sum=0,l,pp; 
	//IF the colimn number is 0 then return 0 
	if (k>=cols){an[i][j][k]=0; }
	if (j<i) {an[i][j][k]=0; }
	//initialize fn(1,1,n), fn(2,2,n), fn(3,3,n) etc. 
	if(k==cols-1 && i==j) an[i][j][k]=a[i][k]; 
	   sum=pref[j][k]-pref[i-1][k]; // New line 
	// calculate f1, f2, f3 
	 f1=an[i][j][k+1]+sum; 
	 f2=an[i+1][j][k] + a[i][k];; 
	 f3=an[i][j-1][k]+a[j][k]; 
	//return the maximum of f1,f2,f3 
	 if (f1>=f2 && f1>=f3) {an[i][j][k]=f1; bn[i][j][k]=1;} 
	  else{ 
		if(f2>=f1 && f2>=f3) {an[i][j][k]=f2; bn[i][j][k]=2;} 
	      else {an[i][j][k]=f3; bn[i][j][k]=3;} 
	} 
}