题目的主要信息：

• A是个$xx$行$yy$列的矩阵，B是个$yy$行$zz$列的矩阵，把A和B相乘，其结果将是另一个$xx$行$zz$列的矩阵C
• 输出这个矩阵C

方法一：暴力法

具体做法：

直接遍历二维矩阵的每个元素，C矩阵等于AB两个矩阵的行乘列叠加即可。

$C_{ij}={\mathrm{\Sigma }}_{k=0}^{y-1}{A}_{ik}{B}_{kj}C\_\{ij\}=\backslash Sigma\; ^\{y-1\}\; \_\{k=0\}\; A\_\{ik\}\; B\_\{kj\}$，其中

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int x, y, z;
    while(cin >> x >> y >> z){
        vector<vector<int> > A(x, vector<int>(y, 0));
        vector<vector<int> > B(y, vector<int>(z, 0));
        for(int i = 0; i < x; i++) //输入两个矩阵
            for(int j = 0; j < y; j++)
                cin >> A[i][j];
        for(int i = 0; i < y; i++)
            for(int j = 0; j < z; j++)
                cin >> B[i][j];
        vector<vector<int> > C(x, vector<int>(z, 0)); //构建结果矩阵
        for(int i = 0; i < x; i++) //遍历相乘相加
            for(int j = 0; j < y; j++)
                for(int k = 0; k < z; k++)
                    C[i][k] += A[i][j] * B[j][k]; //行*列相加
        for(int i = 0; i < x; i++){ //输出
            for(int j = 0; j < z; j++)
                cout << C[i][j] << " ";
            cout << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(xyz)O(xyz)$，三层循环，全部遍历
• 空间复杂度：$O(1)O(1)$，ABC三个矩阵都是必要空间，无额外空间

方法二：暴力法缓存优化

具体做法：

调换代码顺序，依据cpu连续读取的特性，优先访问A[i][k]，利用更多的空间连续性，虽然时间复杂度没有变，但是可以节省更多时间。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int x, y, z;
    while(cin >> x >> y >> z){
        vector<vector<int> > A(x, vector<int>(y, 0));
        vector<vector<int> > B(y, vector<int>(z, 0));
        for(int i = 0; i < x; i++) //输入两个矩阵
            for(int j = 0; j < y; j++)
                cin >> A[i][j];
        for(int i = 0; i < y; i++)
            for(int j = 0; j < z; j++)
                cin >> B[i][j];
        vector<vector<int> > C(x, vector<int>(z, 0)); //构建结果矩阵
        int temp;
        for(int i = 0; i < x; i++)
            for(int k = 0; k < y; k++){
                temp = A[i][k];  //优先访问这个元素
                for(int j = 0; j < z; j++)
                    C[i][j] += temp * B[k][j]; //行*列相加，这一行访问不中断
            }
        for(int i = 0; i < x; i++){ //输出
            for(int j = 0; j < z; j++)
                cout << C[i][j] << " ";
            cout << endl;
        }
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(xyz)O(xyz)$，三层循环，全部遍历
• 空间复杂度：$O(1)O(1)$，ABC三个矩阵都是必要空间，无额外空间