Posted on 2012-03-15 09:39
hoshelly 阅读(722)
评论(0) 编辑 收藏 引用 所属分类:
Programming
Description
在一个二维矩阵中,如果某个位置的数值是该行最大值,同时也是该列最小值,我们则称该位置是矩阵的鞍点。鞍点在工业控制,建筑力学等方面有着广泛应用。鞍点可能有多个,也可能没有。
请编写程序找出矩阵的鞍点。
Input
第一行输入T表示有T个测试实例
第二行输入两个参数A和B,分别表示矩阵的行数和列数
第三行输入二维矩阵的数据,假定数据都是正整数
以此类推输入下个实例
Output
输出鞍点所在的行号和列号,行号和列号都是从0开始编号。
如果存在多个鞍点,输出行号和列号最小的鞍点。如果不存在鞍点,输出-1 -1
Sample Input
2
3 3
11 77 33
44 66 55
22 88 99
4 2
22 11
33 44
55 66
11 88
Sample Output
1 1
-1 -1
#include<iostream>
using namespace std;
int main()
{
int n,max,i,j,k,flag,row_i,row_j;
int a[100][100];
cin>>n;
while(n--)
{
cin>>row_i>>row_j;
for(i=0;i<row_i;i++)
{
for(j=0;j<row_j;j++)
{
cin>>a[i][j];
}
}
for(i=0;i<row_i;i++)
{
max=0;
flag=1;
for(j=0;j<row_j;j++)
{
if(a[i][j]>a[i][max])
max=j;
}
for(k=0;k<row_j;k++)
{
if(a[i][k]==a[i][max] && max!=k)
{
flag=0;
break;
}
}
if(flag==1)
{
for(k=0;k<row_i;k++)
{
if(a[k][max]<=a[i][max] && k!=i)
{
flag=0;
break;
}
}
}
if(flag==1)
{
cout<<i<<" "<<max<<endl;
break;
}
}
if(flag==0)
{
cout<<"-1"<<" "<<"-1"<<endl;
}
}
return 0;
}