深度优先搜索算法求解矩阵最大乘积之和

本代码实现了一个深度优先搜索（DFS）算法，用于找到给定矩阵对 'p' 和 'q' 的最大乘积之和。

算法流程:

输入: 读取两个大小为 n × n 的矩阵 'p' 和 'q'，以及矩阵维度 'n'。
初始化: 初始化全局变量 'ans' 为 -1，表示最大乘积之和的初始值。创建访问标记数组 'vis' 和步长数组 'step'，初始值为全 0。
深度优先搜索 (DFS):
- 递归函数 'dfs' 接受以下参数:
  - 'i': 当前搜索的层次
  - 'p': 矩阵 'p'
  - 'q': 矩阵 'q'
  - 'vis': 访问标记数组
  - 'step': 步长数组
- 递归终止条件: 当搜索到达最后一层 (i == n)，计算当前步长数组 'step' 对应的矩阵元素乘积之和，并与 'ans' 比较更新最大值。
- 遍历所有可能的选择: 对于当前层次 'i'，遍历所有可能的选择 (j 取值范围为 0 到 n-1)，如果该选择未被访问过 (vis[j] 等于 0)，则标记该选择为已访问 (vis[j] 设为 1)，将该选择保存到步长数组 'step' 的第 'i' 个位置，然后递归调用 'dfs' 函数进行下一层次的搜索。
- 回溯: 在回溯时，重置步长数组 'step' 的第 'i' 个位置为 0，并取消对该选择的访问标记。
输出: 输出最大乘积之和 'ans'。

代码实现:

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

int ans = -1; // 用于保存最大乘积之和的全局变量

// 深度优先搜索函数
void dfs(int i, vector<vector<int>>& p, vector<vector<int>>& q, vector<int>& vis, vector<int>& step)
{
    int n = p.size();

    // 如果搜索到达最后一层，则计算乘积之和并更新最大值
    if (i == n) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += p[i][step[i]] * q[step[i]][i];
        if (sum > ans)
            ans = sum;
        return;
    }

    // 遍历当前层次的所有可能选择
    for (int j = 0; j < n; j++) {
        if (vis[j] == 0) { // 如果该选择未被访问过
            vis[j] = 1; // 标记该选择为已访问
            step[i] = j; // 保存该选择到步长数组中的第 i 个位置
            dfs(i + 1, p, q, vis, step); // 递归调用进行下一层次的搜索
            step[i] = 0; // 回溯时重置步长数组中的第 i 个位置为 0
            vis[j] = 0; // 取消对该选择的访问标记
        }
    }
}

int main()
{
    int n;
    cin >> n; // 读取矩阵的维度

    // 创建大小为 n × n 的二维向量 p 和 q 作为输入矩阵
    vector<vector<int>> p(n, vector<int>(n, 0));
    vector<vector<int>> q(n, vector<int>(n, 0));

    // 创建访问标记数组和步长数组，初始值为全 0
    vector<int> vis(n, 0);
    vector<int> step(n, 0);

    // 读取矩阵 p 的元素值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
        }
    }

    // 读取矩阵 q 的元素值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> q[i][j];
        }
    }

    // 调用深度优先搜索函数进行搜索
    dfs(0, p, q, vis, step);

    // 输出最大乘积之和
    cout << ans << endl;

    return 0;
}

流程图:

代码说明:

dfs 函数使用递归的方式遍历所有可能的矩阵元素组合，并计算相应的乘积之和。
vis 数组用于记录每个元素是否被访问过，避免重复访问。
step 数组记录当前路径选择的元素索引，用于计算乘积之和。
ans 变量用于记录最大乘积之和，并不断更新。

总结:

这段代码使用深度优先搜索算法，通过遍历所有可能的矩阵元素组合，找到了给定矩阵对的最大乘积之和。该算法的时间复杂度为 O(n!)，其中 'n' 为矩阵的维度。