Question

跪求这道C++编程题怎么做，毫无思路啊

Answer 1

//把矩阵每一行位移0~6次，所有情况都求一遍就行了，n才只有7.
#include<iostream>

using namespace std;
int a[7][7];

int main()
{
	int n;
	cin >> n;
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			cin >> a[i][j];
	int ans=70000;
	for (int move1=0; move1<=6; move1++)
	for (int move2=0; move2<=6; move2++)
	for (int move3=0; move3<=6; move3++)
	for (int move4=0; move4<=6; move4++)
	for (int move5=0; move5<=6; move5++)
	for (int move6=0; move6<=6; move6++)
	{
		int maxsum=0;
		for (int j=0; j<=6; j++)
		{
			int sum=a[0][j]+a[1][j+move1]+a[2][j+move2]+a[3][j+move3]
						   +a[4][j+move4]+a[5][j+move5]+a[6][j+move6];
			if (maxsum<sum) maxsum=sum;
		}
		if (ans>maxsum) ans=maxsum;
	}
	cout << ans << endl;
}
//如果你学过递归什么的，就把那六层循环用递归重写。
//以及我只写了处理一次数据的，如果你要解决问题，应该添加对多组数据的处理。

追答

经评论提醒，代码中的j+move都应该改为(j+move)%7，否则会出现数组越界的情况。

Answer 2

所有情况遍历一次时间复杂度O(m^n)肯定不行的呀...
令sum[]是每列和的数组, 对sum[]赋初值为输入的矩阵mat[][]的第1行的值, 同时求sum[]中元素的最大值minSumMax
从第二行开始, 尝试左移n次, 求sum[]与当前行每列的和tmpSum[], 求tmpSum[]中元素最大值tmpSumMax, 同时记minTmpSumMax, 当tmpSumMax < minTmpSumMax时, 将tmpSum[]复制为minTmpSum[], 最后用minTmpSum[]覆盖sum[]
这样共尝试了m*n次, 只要从第二行开始都保持每行左移n次后使得minSumMax最小就可以

追问

这个思路怎么写出来呢？

Answer 3

应该是与八皇后类似的吧