一、背景故事

鞍点指的是矩阵中的一个元素，它是所在行的最大值，同时是所在列的最小值。

给定一个矩阵，假设每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点。

例如：在下面的例子中（第4行第1列的元素就是鞍点，值为8 ）。

11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8 6 4 7 2
15 10 11 20 25

二、实验目标

输入包含一个n*n的矩阵，如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出"not found"

注意：鞍点的行列下标是从1到n来计算的。

输入样例1：

5
11 3 5 6  9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25

输出样例1：

4 1 8

数据范围：1<=n<=10

二、分析

1、思路

根据题目描述，如果有一个点，在其所在行里是最大，而在其所在列里是最小，则这个点就是鞍点。

那么就可以按照每行找到最大值，然后对最大值所在的列求最小值，假如最小值和最大值相等（因为都只有一个，相等就表示是同一个点），这个点就是鞍点。

2、算法－枚举：

• 穷举每个行，
  • 计算一行的最大值（及列下标）
  • 计算最大值所在列的最小值
  • 判定最大值和最小值是否相等，如果相等就输出鞍点信息，然后break循环
• 如果正常结束（表示没有鞍点），输出"not found"

三、AC代码

#include<iostream>
using namespace std;

int n, a[15][15];

int main()
{
  cin >> n;
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= n; j++)
    {
      cin >> a[i][j];
    }
  }
  bool f = false;
  for(int i = 1; i <= n; i++)
  {
    int mx = -0x3f3f3f3f, lie;
    for(int j = 1; j <= n; j++)
    {
      if(a[i][j] > mx)
      {
        mx = a[i][j];
        lie = j;
      }
    }
    int mi = 0x3f3f3f3f, hang;
    for(int j = 1; j <= n; j++)
    {
      if(a[j][lie] < mi)
      {
        mi = a[j][lie];
        hang = j;
      }
    }
    if(mx == mi)
    {
      f = true;
      cout << hang << " " << lie << " " << a[hang][lie] << endl;
    }
  }
  if(f == false)
  {
    cout << "not found";
  }
  return 0;
}