#include <stdio.h>
#include <stdlib.h>

#define N 2 // 矩阵大小

void matrix_multiply(int A[][N], int B[][N], int C[][N])
{
    int i, j, k;
    if (N == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }  else  {
        int A11[N / 2][N / 2], A12[N / 2][N / 2], A21[N / 2][N / 2], A22[N / 2][N / 2];
        int B11[N / 2][N / 2], B12[N / 2][N / 2], B21[N / 2][N / 2], B22[N / 2][N / 2];
        int C11[N / 2][N / 2], C12[N / 2][N / 2], C21[N / 2][N / 2], C22[N / 2][N / 2];
        int P[N / 2][N / 2], Q[N / 2][N / 2], R[N / 2][N / 2], S[N / 2][N / 2], 
                 T[N / 2][N / 2], U[N / 2][N / 2], V[N / 2][N / 2];
        // 将矩阵分成4个小矩阵
        for (i = 0; i < N / 2; i++)   {
            for (j = 0; j < N / 2; j++)     {
                A11[i][j] = A[i][j];
                A12[i][j] = A[i][j + N / 2];
                A21[i][j] = A[i + N / 2][j];
                A22[i][j] = A[i + N / 2][j + N / 2];
                B11[i][j] = B[i][j];
                B12[i][j] = B[i][j + N / 2];
                B21[i][j] = B[i + N / 2][j];
                B22[i][j] = B[i + N / 2][j + N / 2];
            }
        }
        // 求7个小矩阵
        matrix_multiply(A11, B11, P);
        matrix_multiply(A12, B21, Q);
        matrix_multiply(A11, B12, R);
        matrix_multiply(A12, B22, S);
        matrix_multiply(A21, B11, T);
        matrix_multiply(A22, B21, U);
        matrix_multiply(A21, B12, V);

        // 根据公式计算四个子矩阵
        for (i = 0; i < N / 2; i++)        {
            for (j = 0; j < N / 2; j++)          {
                C11[i][j] = P[i][j] + Q[i][j];
                C12[i][j] = R[i][j] + S[i][j];
                C21[i][j] = T[i][j] + U[i][j];
                C22[i][j] = V[i][j] + P[i][j] - R[i][j] + T[i][j];
            }
        }
        // 将四个子矩阵合并成一个大矩阵
        for (i = 0; i < N / 2; i++)        {
            for (j = 0; j < N / 2; j++)           {
                C[i][j] = C11[i][j];
                C[i][j + N / 2] = C12[i][j];
                C[i + N / 2][j] = C21[i][j];
                C[i + N / 2][j + N / 2] = C22[i][j];
            }
        }
    }
}

int main()
{
    int A[N][N] = {{1, 2}, {3, 4}};
    int B[N][N] = {{5, 6}, {7, 8}};
    int C[N][N];
    int i, j;

    matrix_multiply(A, B, C);

    printf("矩阵A:\n");
    for (i = 0; i < N; i++)    {
        for (j = 0; j < N; j++)        {
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }

    printf("矩阵B:\n");
    for (i = 0; i < N; i++)    {
        for (j = 0; j < N; j++)        {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }

    printf("矩阵C:\n");
    for (i = 0; i < N; i++)    {
        for (j = 0; j < N; j++)        {
            printf("%d ", C[i][j]);
        }
        printf("\n");
    }
    return 0;
}