[递归] 平衡矩阵

平衡矩阵

题目描述

现在有一个n阶正整数方阵（n<=7），现在可以对矩阵的任意一行进行左移，具体操作为：每次对于某一行a_i1,a_i2,…,a_in进行一次左移，最左边的元素移动到这一行的末尾，其他元素均向左移动一位，即变为a_i2,a_i3,…,a_in,a_i1。对某一行可以执行任意次的左移。
现在我们的目标是：通过对矩阵的每一行进行若干次左移，使得矩阵中每列和的最大值最小。

关于输入

输入包含多组数据。
对于每组数据，第一行为一个正整数n（1<=n<=7），代表矩阵的阶。接下来的n行，每行n个正整数（不超过10000），代表这个矩阵。
输入数据以一个-1为结尾代表输入结束。

关于输出

对于每组数据，输出一行一个正整数，为最小的最大列和。

例子输入

2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1

例子输出

11
15

解题分析

主要思路是，通过深度优先搜索遍历所有可能的矩阵状态，然后在所有状态中找到最小的最大列和。在搜索过程中，我们对每一行进行所有可能的左移操作，并通过更新最小的最大列和来保证找到的是最优解。

代码实现

#include <iostream>
using namespace std;

int m[8][8]={0};
int n;
int result;
int flag=0;

void zy(int m[8][8],int row){
    int temp1=m[row][0];
    for(int i=0;i<n-1;i++){
        m[row][i]=m[row][i+1];
    }
    m[row][n-1]=temp1;
}

int getmax(int m[8][8]){
    int max1=0;
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<n;j++){
            sum+=m[j][i];
        }
        max1=max1>sum?max1:sum;
    }
    return max1;
}

void dfs(int m[8][8],int row){
    if(row==n){
        return;
    }
    for(int i=0;i<n;i++){
        zy(m,row);
        int a=getmax(m);
        result=result<a?result:a;
        dfs(m,row+1);
    }
}

int main() {
    while(cin>>n){
        if(n==-1) break;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                cin>>m[i][j];
            }
        result=getmax(m);
        dfs(m,0);
        cout<<result<<endl;
    }
	return 0;
}

进一步解释

这个程序的主要目标是通过对矩阵的每一行进行若干次左移，使得矩阵中每列和的最大值最小。程序采用了深度优先搜索（DFS）的方法来实现这个目标。

以下是程序的详细解释：

1. **全局变量的定义**

```c++
int m[8][8] = {0};
int n;
int result;
int flag = 0;
```

`m` 是一个二维数组，用于存储输入的矩阵；`n` 是矩阵的阶数；`result` 用于存储当前找到的最小的最大列和；`flag` 是一个标志变量，用于标记搜索过程中的状态。

2. **左移操作函数**

```c++
void zy(int m[8][8], int row) {
    int temp1 = m[row][0];
    for (int i = 0; i < n - 1; i++) {
        m[row][i] = m[row][i + 1];
    }
    m[row][n - 1] = temp1;
}
```

`zy` 函数实现了对矩阵中一行的左移操作。它首先保存第一个元素，然后把后面的元素向前移动一位，最后把保存的第一个元素放到最后。

3. **计算最大列和函数**

```c++
int getmax(int m[8][8]) {
    int max1 = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += m[j][i];
        }
        max1 = max1 > sum ? max1 : sum;
    }
    return max1;
}
```

`getmax` 函数计算矩阵中的最大列和。它遍历每一列，计算列和，然后更新最大列和。

4. **深度优先搜索函数**

```c++
void dfs(int m[8][8], int row) {
    if (row == n) {
        return;
    }
    for (int i = 0; i < n; i++) {
        zy(m, row);
        int a = getmax(m);
        result = result < a ? result : a;
        dfs(m, row + 1);
    }
}
```

`dfs` 函数实现了深度优先搜索。它对当前行进行左移操作，然后计算最大列和，更新最小的最大列和，然后对下一行进行搜索。这个过程会对每一行进行所有可能的左移操作，并通过深度优先搜索找到所有可能的矩阵状态，从而找到最小的最大列和。

5. **主函数**

```c++
int main() {
    while (cin >> n) {
        if (n == -1) break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                cin >> m[i][j];
            }
        result = getmax(m);
        dfs(m, 0);
        cout << result << endl;
    }
    return 0;
}
```

`main` 函数首先读取输入数据，然后调用 `dfs` 函数进行搜索。最后输出找到的最小的最大列和。