天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

鞍点定位问题

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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理