#include <stdio.h>    // ket nxn-es martix szorzasa Strassen-modszerrel, ahol n ketto hatvanya
#include <stdlib.h>

FILE * f;

int ** lefoglal(int n)      // dinamikusan helyet foglal egy matrixnak 	
{          int i;
	   int **m=(int**)malloc(n*sizeof(int*));
           for (i=0; i<n;i++) 
                m[i]=(int*)malloc(n*sizeof(int));
return m;
}

void felszabadit(int **x, int n)  // felszabaditja egy matrix helyet
{ 
     int i;
     for (i=0; i<n; i++) free(x[i]);
     free(x);
}

void listaz(int **x, int n)   // kilistaz egy matrixot
{  
       int i,j;
       for (i=0; i<n;i++)
       {
	 for (j=0; j<n;j++) printf(" %4d ", x[i][j]);
         printf("\n");
       }
};


int **  add(int **x, int **y, int n)   // összead két matrixot

{  
  int ** z = lefoglal(n);
  int i,j;

  for (i=0; i<n;i++)
     for (j=0; j<n;j++) z[i][j]=x[i][j]+y[i][j];
  return z;
};

int **  sub(int **x, int **y, int n)   // kivon egy matrixot egy masikbol
{  
   int ** z = lefoglal(n);
   int i,j;

   for (i=0; i<n;i++)
      for (j=0; j<n;j++) z[i][j]=x[i][j]-y[i][j];
   return z;
};

int ** valaszt (int **x, int p, int n)    // egy nxn-es matrixbol kivalaszt egy n/2 x n/2-es reszmatrixot
{
   int r,s,k,l;
   int m= n / 2;
   int **y = lefoglal(m);
   switch(p)
   {
    case 11 :  k=0; l=0; break; 
    case 12 :  k=0, l=m; break;
    case 21 :  k=m; l=0; break; 
    case 22 :  k=m; l=m; break;
   } 
   for (r=0; r<m; r++)
      for (s=0; s<m; s++) y[r][s]=x[k+r][l+s];
  return y;
}

int ** betesz (int **c11, int **c12, int **c21, int **c22, int n)  // negy n/2 x n/2-es matrixbol keszit egy nxn-eset
{
  int r,s,k,l; 
  int m= n / 2;
  int ** y=lefoglal(n);

  k=0; l=0;  
  for (r=0; r<m; r++)
      for (s=0; s<m; s++) y[k+r][l+s]= c11[r][s];
 
  k=0, l= m; 
  for (r=0; r<m; r++)
      for (s=0; s<m; s++) y[k+r][l+s]= c12[r][s];
 
  k=m; l=0;  
  for (r=0; r<m; r++)
      for (s=0; s<m; s++) y[k+r][l+s]= c21[r][s];
  
  k=m; l=m; 
  for (r=0; r<m; r++)
      for (s=0; s<m; s++) y[k+r][l+s]= c22[r][s];  
  return y;
}

int **  mult(int **a, int **b, int n)     // Strassen-modszerrel osszeszoroz ket matrixot
{    
   int **x1,**x2,**x3,**x4,**x5,**x6,**x7;
   int **c11, **c12, **c21, **c22, **c;
   int m;
		
   c=lefoglal(n);
   if (n>1)
   {
     m= n/2, 
     x1=lefoglal(m); x2=lefoglal(m);x3=lefoglal(m);x4=lefoglal(m);x5=lefoglal(m);
     x6=lefoglal(m);x7=lefoglal(m);
     c11= lefoglal(m); c12= lefoglal(m); c21= lefoglal(m); c22= lefoglal(m);
        	
     x1= mult(add(valaszt(a,11,n),valaszt(a,22,n), m), add(valaszt(b,11,n),valaszt(b,22,n),m), m);
     x2= mult(add(valaszt(a,21,n),valaszt(a,22,n), m), valaszt(b,11,n), m);       
     x3= mult(valaszt(a,11,n),sub(valaszt(b,12,n), valaszt(b,22,n), m),m);
     x4= mult(valaszt(a,22,n),sub(valaszt(b,21,n), valaszt(b,11,n), m),m);
     x5= mult(add(valaszt(a,11,n),valaszt(a,12,n), m), valaszt(b,22,n), m);
     x6= mult(sub(valaszt(a,21,n),valaszt(a,11,n), m), add(valaszt(b,11,n),valaszt(b,12,n),m), m);
     x7= mult(sub(valaszt(a,12,n),valaszt(a,22,n), m), add(valaszt(b,21,n),valaszt(b,22,n),m), m);

     c11=add(sub(add(x1,x4,m),x5,m),x7,m);
     c12=add(x3,x5,m);
     c21=add(x2,x4,m);
     c22=add(sub(add(x1,x3,m),x2,m),x6,m);
        
     c=betesz(c11,c12,c21,c22,n);
     
     felszabadit(x1,m);felszabadit(x2,m);felszabadit(x3,m);felszabadit(x4,m);felszabadit(x5,m);
     felszabadit(x6,m);felszabadit(x7,m);
     felszabadit(c11,m); felszabadit(c12,m); felszabadit(c21,m); felszabadit(c22,m);
    }
    else  c[0][0]= a[0][0]*b[0][0];    
    return c;
};


int main()
{

 f= fopen("be.txt","r");

 int i,j;
 int n;
 int **a, **b, **c;


 fscanf(f,"%d", &n);    // allomanybol olvassa az n erteket, amely kettonek hatvanya kell, hogy legyen, 
                        // de ezt nem ellenorzi a program
 
 a=lefoglal(n);        // helyet foglal az a matrixnak
 b=lefoglal(n);        // helyet foglal az b matrixnak    

 for (i=0; i<n; i++)
  for (j=0; j<n; j++) fscanf(f,"%d", &a[i][j]); 

 for (i=0; i<n; i++)
  for (j=0; j<n; j++) fscanf(f,"%d", &b[i][j]); 

 listaz(a,n);         // kilistazza az a matrixot
 printf("\n");

 listaz(b,n);         // kilistazza a b matrixot
 printf("\n");
                          
 c=lefoglal(n);
 c=mult(a,b,n);        // osszeszorozza a ket matrixot, c=a*b 

 listaz(c,n);         // kilistazza a c matrixot
 printf("\n");

 return 0;

}