A41029. 矩阵
填空题
困难
知识点
题目描述
矩阵
题目描述
给一个n*n的矩阵A，它的每一个元素Ai,j都是整数( 0 <= i < n, 0 <= j < n )。在每一行i( 0 <= i < n )给一个右移操作，使第i行的整数整体向右移动一个位置，最右边的整数将会移动到最左端的那一列。
你可以在任意行做右移操作，这样你会得到一个新的矩阵，对于新的矩阵你当然也可以做右移操作。你的任务就是求列最小值ColMin,它是每个矩阵的列最大值，但同时又是所有矩阵中的列最小值。
max(0 <= j < n){Cj|Cj=Σ0<=i < nAi,j}
输入格式
可能包含多次输入。第一行是一个整数n，接下来n行每行包含n个整数，这些数据就是n*n的矩阵A的元素。如果输入仅含有-1的一行，就表示输入终止。其中1 <= n <= 7 而且 |Ai,j| < 104 。
输出格式
对于每组测试，打印一行包含一个数值，它在一个矩阵中是列最大值，但是在所有的变换矩阵中又是列最小值。
样例输入
2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1
样例输出
11
15
参考答案
#include <stdio.h>
int a[7][7];
int b[7];//记录矩阵的每一行最多移动的次数
int n;
int max()//求出每次移动一行之后的矩阵的“列元素和”最大值
{
int i,j,tmp,res=-1;
for(j=0;j<n;j++)
{
tmp=0;
for(i=0;i<n;i++)
tmp +=a[i][j];
if(tmp>res) res=tmp;
}
return res;
}
void move(int i)//移动矩阵第i行
{
int k,j,tmp;
tmp=a[i][n-1];
for(j=n-1;j>0;j--)
a[i][j]=a[i][j-1];
a[i][0]=tmp;
}
int main()
{
int i,j,k,min,m;
while(scanf("%d",&n)&&n>0)
{
//初始化
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",a[i]+j);
for(i=0;i<n;i++)
b[i]=1;
min=100000;
int flag=1;
while(flag){
flag=0;
for(i=n-1;i>=0;i--){
if(b[i]<=n)
{
b[i]++;
move(i);
m=max();
if(m<min) min=m;
for(k=i+1;k<n;k++)
b[k]=1;
flag=1;
break;
}
}
}
printf("%d\n",min);
}
return 0;
}
上一题
下一题