#include<stdio.h>
int n;

void strassen(int a[][n],int b[][n],int c[][n],int size)
{
 int p1[size/2][size/2];
 int p2[size/2][size/2];
 int p3[size/2][size/2];
 int p4[size/2][size/2];
 int p5[size/2][size/2];
 int p6[size/2][size/2];
 int p7[size/2][size/2];

 int temp1[size/2][size/2];
 int temp2[size/2][size/2];

 int i,j;

 if(size>=2)
 {
  //To calculate part1 i.e. p1=(A00+A11)*(B00+B11)
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p1
    temp1[i][j]=a[i][j]+a[i+size/2][j+size/2];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p1
    temp2[i][j]=b[i][j]+b[i+size/2][j+size/2];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p1,n);

  // To Calculate Part2 i.e. p2=(A10+A11)*B00
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p2
    temp1[i][j]=a[i+size/2][j]+a[i+size/2][j+size/2];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p2
    temp2[i][j]=b[i][j];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p2,n);

  // To Calculate Part3 i.e. p3=A00*(B01-B11)
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p3
    temp1[i][j]=a[i][j];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p3
    temp2[i][j]=b[i][j+size/2]-b[i+size/2][j+size/2];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p3,n);

  // To Calculate Part4 i.e. p4=A11*(B10-B00)
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p4
    temp1[i][j]=a[i+size/2][j+size/2];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p4
    temp2[i][j]=b[i+size/2][j]-b[i][j];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p4,n);
  
  // To Calculate Part5 i.e. p5=(A00+A01)*B11
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p5
    temp1[i][j]=a[i][j]+a[i][j+size/2];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p5
    temp2[i][j]=b[i+size/2][j+size/2];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p5,n);
 
  // To Calculate Part6 i.e. p6=(A10-A00)*(B00+B01)
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p6
    temp1[i][j]=a[i+size/2][j]-a[i][j];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p6
    temp2[i][j]=b[i][j]+b[i][j+size/2];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p6,n);
  
  // To Calculate Part7 i.e. p7=(A01-A11)*(B10+B11)
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //half sub part of p7
    temp1[i][j]=a[i][j+size/2]-a[i+size/2][j+size/2];
   } 
  }
  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    //second sub part of p7
    temp2[i][j]=b[i+size/2][j]+b[i+size/2][j+size/2];
   } 
  }
  n=size/2;
  printf("\n n=%d",n);
  strassen(temp1,temp2,p7,n);

  
  //these value p1.....p7 are put in to following formula to get actual result here as product in matrix c

 
  //To Calculate C11=p1+p4-p5+p7
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    c[i][j]= p1[i][j]+p4[i][j]-p5[i][j]+p7[i][j];
   }
  }

  //To Calculate C12=p3+p5
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    c[i][j+size/2]= p3[i][j]+p5[i][j];
   }
  }
  
  //To Calculate C21=p2+p4
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    c[i+size/2][j]= p2[i][j]+p4[i][j];
   }
  }
 
  //To Calculate C22=p1+p3-p2+p6  
  for(i=0;i<size/2;i++)
  {
   for(j=0;j<size/2;j++)
   {
    c[i+size/2][j+size/2]= p1[i][j]+p3[i][j]-p2[i][j]+p6[i][j];
   }
  } 
 
 }
 else if(size==1)
 {
  c[0][0]=a[0][0]*b[0][0];
 } 

}

int main()
{
 int i,j,temp;

 printf("\nEnter the Size of NXN Matrix:");
 scanf("%d",&n);

 temp=n;

 if(n<=0)
  return 0;

 int a[n][n];
 int b[n][n];
 int c[n][n];

 printf("\nEnter Matrix A:\n"); 
 for(i=0;i<temp;i++)
 {
  for(j=0;j<temp;j++)
  {
   scanf("%d",&a[i][j]);
  }
 }

 printf("\nEnter Matrix B:\n"); 
 for(i=0;i<temp;i++)
 {
  for(j=0;j<temp;j++)
  {
   scanf("%d",&b[i][j]);
  }
 }

 printf("\nMatrix A:\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   printf("\t %d",a[i][j]);
  }
  printf("\n");
 }
 
 printf("\nMatrix B:\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   printf("\t %d",b[i][j]);
  }
  printf("\n");
 }

 strassen(a, b, c, n);
 printf("\nMatrix :\n");
 for(i=0;i<temp;i++)
 {
  for(j=0;j<temp;j++)
  {
   printf("\t %d",c[i][j]);
  }
  printf("\n");
 }

 return 0;

}

/*
OUTPUT-

[ProfessionalCipher@www.professionalcipher.blogspot.com]$ gcc Newfile.c                                                                                                                                                                                
[ProfessionalCipher@www.professionalcipher.blogspot.com]$ ./a.out                                                                                                                                                                                      
                                                                                                                                                                                                     
Enter the Size of NXN Matrix:2                                                                                                                                                                       
                                                                                                                                                                                                     
Enter Matrix A:                                                                                                                                                                                      
1                                                                                                                                                                                                    
2                                                                                                                                                                                                    
3                                                                                                                                                                                                    
4                                                                                                                                                                                                    
                                                                                                                                                                                                     
Enter Matrix B:                                                                                                                                                                                      
4                                                                                                                                                                                                    
3                                                                                                                                                                                                    
2                                                                                                                                                                                                    
1

Matrix A:                                                                                                                                                                                            
         1       2                                                                                                                                                                                   
         3       4                                                                                                                                                                                   
                                                                                                                                                                                                     
Matrix B:                                                                                                                                                                                            
         4       3                                                                                                                                                                                   
         2       1                                                                                                                                                                                   
                                                                                                                                                                                                     
 n=1                                                                                                                                                                                                 
 n=1                                                                                                                                                                                                 
 n=1                                                                                                                                                                                                 
 n=1                                                                                                                                                                                                 
 n=1                                                                                                                                                                                                 
 n=1
 Matrix :                                                                                                                                                                                             
         8       5                                                                                                                                                                                   
         20      13                                                                                                                                                                                  
[ProfessionalCipher@www.professionalcipher.blogspot.com]$                 
*/