Posted on 2012-03-15 09:39
hoshelly 閱讀(729)
評論(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;
}