如果矩阵A中存在这样的一个元素A[i][j]满足下列条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。请编写程序求出矩阵A的马鞍点。 输入格式: 首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。 对于每组测试数据,首先输入2个正整数m、n(1 ≤ m,n ≤ 100),分别表示二维数组的行数和列数。 然后是二维数组的信息,每行数据之间用一个空格分隔,每个数组元素均在int型范围内。简单起见,假设二维数组的元素各不相同,且每组测试数据最多只有一个马鞍点。 输出格式: 对于每组测试数据,若马鞍点存在则输出其值,否则输出“Impossible”。注意,引号不必输出。
时间: 2024-02-26 18:59:04 浏览: 98
好的,我会帮你解决这个问题。以下是 C++ 的代码实现:
```c++
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N];
int main()
{
int t;
cin >> t;
while (t -- )
{
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i ++ )
for (int j = 0; j < n; j ++ )
cin >> a[i][j];
int ans = -1;
for (int i = 0; i < m; i ++ )
{
int k = 0;
for (int j = 1; j < n; j ++ )
if (a[i][j] < a[i][k])
k = j;
bool f = true;
for (int j = 0; j < m; j ++ )
if (a[j][k] > a[i][k])
{
f = false;
break;
}
if (f)
{
ans = a[i][k];
break;
}
}
if (ans == -1)
cout << "Impossible" << endl;
else
cout << ans << endl;
}
return 0;
}
```
思路很简单,对于每一行,我们找到它的最小值,然后在该列中找到最大值,如果该值为该列中最大值,那么它就是一个马鞍点。
阅读全文