Posted on 2012-03-15 09:39
hoshelly 閱讀(728)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Programming
Description
在一個(gè)二維矩陣中，如果某個(gè)位置的數(shù)值是該行最大值，同時(shí)也是該列最小值，我們則稱該位置是矩陣的鞍點(diǎn)。鞍點(diǎn)在工業(yè)控制，建筑力學(xué)等方面有著廣泛應(yīng)用。鞍點(diǎn)可能有多個(gè)，也可能沒有。
請(qǐng)編寫程序找出矩陣的鞍點(diǎn)。
Input
第一行輸入T表示有T個(gè)測(cè)試實(shí)例
第二行輸入兩個(gè)參數(shù)A和B，分別表示矩陣的行數(shù)和列數(shù)
第三行輸入二維矩陣的數(shù)據(jù)，假定數(shù)據(jù)都是正整數(shù)
以此類推輸入下個(gè)實(shí)例
Output
輸出鞍點(diǎn)所在的行號(hào)和列號(hào)，行號(hào)和列號(hào)都是從0開始編號(hào)。
如果存在多個(gè)鞍點(diǎn)，輸出行號(hào)和列號(hào)最小的鞍點(diǎn)。如果不存在鞍點(diǎn)，輸出-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;
}