Code:
#include <iostream>
using namespace std;
void Add(int **A,int **B,int **C,int n)
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
C[i][j]=A[i][j]+B[i][j];
}
return;
}
void subtract(int **A,int **B,int **C,int n)
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
C[i][j]=A[i][j]-B[i][j];
}
return;
}
void AB(int **A,int **B,int **C,int n)
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
C[i][j]=0;
for(int k=0;k<n;++k)
C[i][j]+=A[i][k]*B[k][j];
}
}
}
void strassen(int **A,int **B,int **C,int n)
{
/*
if(n==1)
{
C[0][0]=A[0][0]*B[0][0];
return;
}
*/
if(n<=2)
{
AB(A,B,C,n);
return;
}
int s=n/2;
int **A11=new int*[s];
int **A12=new int*[s];
int **A21=new int*[s];
int **A22=new int*[s];
int **B11=new int*[s];
int **B12=new int*[s];
int **B21=new int*[s];
int **B22=new int*[s];
int **C11=new int*[s];
int **C12=new int*[s];
int **C21=new int*[s];
int **C22=new int*[s];
for(int i=0;i<s;++i)
{
A11[i]=new int[s];
A12[i]=new int[s];
A21[i]=new int[s];
A22[i]=new int[s];
B11[i]=new int[s];
B12[i]=new int[s];
B21[i]=new int[s];
B22[i]=new int[s];
C11[i]=new int[s];
C12[i]=new int[s];
C21[i]=new int[s];
C22[i]=new int[s];
}
for(int i=0;i<s;++i)
{
for(int j=0;j<s;++j)
{
A11[i][j]=A[i][j];
A12[i][j]=A[i][j+s];
A21[i][j]=A[i+s][j];
A22[i][j]=A[i+s][j+s];
B11[i][j]=A[i][j];
B12[i][j]=A[i][j+s];
B21[i][j]=A[i+s][j];
B22[i][j]=A[i+s][j+s];
}
}
int **s1=new int*[s];
int **s2=new int*[s];
int **s3=new int*[s];
int **s4=new int*[s];
int **s5=new int*[s];
int **s6=new int*[s];
int **s7=new int*[s];
int **s8=new int*[s];
int **s9=new int*[s];
int **s10=new int*[s];
int **p1=new int*[s];
int **p2=new int*[s];
int **p3=new int*[s];
int **p4=new int*[s];
int **p5=new int*[s];
int **p6=new int*[s];
int **p7=new int*[s];
for(int i=0;i<s;++i)
{
s1[i]=new int[s];
s2[i]=new int[s];
s3[i]=new int[s];
s4[i]=new int[s];
s5[i]=new int[s];
s6[i]=new int[s];
s7[i]=new int[s];
s8[i]=new int[s];
s9[i]=new int[s];
s10[i]=new int[s];
p1[i]=new int[s];
p2[i]=new int[s];
p3[i]=new int[s];
p4[i]=new int[s];
p5[i]=new int[s];
p6[i]=new int[s];
p7[i]=new int[s];
}
subtract(B12,B22,s1,s);
subtract(B21,B11,s4,s);
subtract(A12,A22,s7,s);
subtract(A11,B21,s9,s);
Add(A11,A12,s2,s);
Add(A21,A22,s3,s);
Add(A11,A22,s5,s);
Add(B11,B22,s6,s);
Add(B21,B22,s8,s);
Add(B11,B12,s10,s);
strassen(A11,s1,p1,s);
strassen(s2,B22,p2,s);
strassen(s3,B11,p3,s);
strassen(A22,s4,p4,s);
strassen(s5,s6,p5,s);
strassen(s7,s8,p6,s);
strassen(s9,s10,p7,s);
Add(p5,p4,C11,s);
subtract(C11,p2,C11,s);
Add(C11,p6,C11,s);
Add(p1,p2,C12,s);
Add(p3,p4,C21,s);
Add(p5,p1,C22,s);
subtract(C22,p3,C22,s);
subtract(C22,p3,C22,s);
for(int i=0;i<s;++i)
{
for(int j=0;j<s;++j)
{
C[i][j]=C11[i][j];
C[i][j+s]=C12[i][j];
C[i+s][j]=C21[i][j];
C[i+s][j+s]=C22[i][j];
}
delete C11[i];
delete C12[i];
delete C21[i];
delete C22[i];
delete A11[i];
delete A12[i];
delete A21[i];
delete A22[i];
delete B11[i];
delete B12[i];
delete B21[i];
delete B22[i];
delete s1[i];
delete s2[i];
delete s3[i];
delete s4[i];
delete s5[i];
delete s6[i];
delete s7[i];
delete s8[i];
delete s9[i];
delete s10[i];
delete p1[i];
delete p2[i];
delete p3[i];
delete p4[i];
delete p5[i];
delete p6[i];
delete p7[i];
}
delete C11;
delete C12;
delete C21;
delete C22;
delete A11;
delete A12;
delete A21;
delete A22;
delete B11;
delete B12;
delete B21;
delete B22;
delete s1;
delete s2;
delete s3;
delete s4;
delete s5;
delete s6;
delete s7;
delete s8;
delete s9;
delete s10;
delete p1;
delete p2;
delete p3;
delete p4;
delete p5;
delete p6;
delete p7;
}
int main()
{
int n;
cin>>n;
int **A=new int*[n],**B=new int*[n],**C=new int*[n];
for(int i=0;i<n;++i)
{
A[i]=new int[n];
B[i]=new int[n];
C[i]=new int[n];
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
A[i][j]=B[i][j]=C[i][j]=j+1;
}
strassen(A,B,C,n);
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
cout<<C[i][j]<<" ";
cout<<endl;
}
for(int i=0;i<n;++i)
{
delete A[i];
delete B[i];
delete C[i];
}
}