计算鞍点

本题为程序设计与算法（一）的测验习题，编号032，具体问题见下，引用自OJ：

总时间限制: 1000ms 内存限制: 65536kB

描述

给定一个5*5的矩阵，每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点。
鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值。
例如：在下面的例子中（第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

输入

输入包含一个5行5列的矩阵

输出

如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出"not found"

样例输入

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

样例输出

4 1 8

这个问题的首先要做的操作就是，读入数组，之后，按行找出当前行的最大值，再按列找出当前列的最小值。

到这之后，我停止了思考，我一时间没办法找到每行最大值和每列最小值有什么关系，转而陷入到了为了找寻关系而绕来绕去的思路。

先看正常情况下，如何建立联系。目标输出的是鞍点的索引及其值。注意到鞍点必须具备两种性质：当前行最大，当前列最小。并且题目已经给出限制，每行、每列只有一个极值。所以，找到每行的最大值，再按列遍历，如果每列的最小值和当前的行最大值相等则一定是鞍点，且唯一。如果对行遍历完之后，没有找到鞍点，则不存在，即not found.

以上判断方法来自：Mariclery的帖子，内包含代码可供查阅。

接下来我要说的是我当时脑子是如何转了个大弯找到奇葩判断方法：

首先，读入数组后，并没有将每行最大值的值和每列最小值的值记录，记录的是值对应的索引，两个数组分别存放每行最大值对应的列索引，和每列最小值对应的行索引。唉，说到这就绕绕的。

接下来，不同于上面老哥的按列遍历，用每行最大值检验是否为鞍点，我的想法是将行最大值坐标顺序列出，列最小坐标顺序列出，如果某点是鞍点，则该行（列）的最大列（最小行）坐标索引对应的最小行（最大列）坐标索引必将等于当前遍历的行（列）索引i。

这也太绕了。

举个例子：

(0,a) (1,b) (2,c) (3,d) (4,e) 为每行最大值的坐标，第一个位置是0~4的行号索引，第二个位置是每行最大值的列索引。
(A,0) (B,1) (C,2) (D,3) (E,4) 为每列最小值的坐标，第一个位置是每列最小值的列索引，第二个位置是0~4的列号索引。

如果 (B,1)是鞍点，则第一行坐标中，B作为行最大值坐标的行索引，即，第一个坐标值等于B的点的第二个坐标值（列索引）一定等于i。

如果用max[5]存放a~e，min[5]存放A~E，可将上述关系写作：

若（min[i],i)是鞍点，则必有max[min[i]]==i

或者：

若（i,max[i])是鞍点，则必有min[max[i]]==i

试图描述清楚这种关系是费劲的。我也因为一时的脑抽，陷入找索引之间的关系迟迟没有结果，时间久，想的脑子也痛。

下面放出源代码：

#include<cstdio>
int main(){
	int a[5][5];
	for(int i=0;i<5;i++)	for(int j=0;j<5;j++)	scanf("%d",&a[i][j]);
	int max_r[5],min_c[5];
	for(int i;i<5;i++) max_r[i]=0,min_c[i]=0;
	for(int i=0;i<5;i++){
		for (int j=0;j<5;j++){
			if(a[i][j]>a[i][max_r[i]]) max_r[i]=j;//存储每行的最大值的列索引
			if(a[j][i]<a[min_c[i]][i]) min_c[i]=j;//存储每列的最小值的行索引
		}
	}
	for(int i=0;i<5;i++) if(max_r[min_c[i]]==i) // 若（min[i],i)是鞍点，则必有max[min[i]]==i
	{
		printf("%d %d %d\n",min_c[i]+1,i+1,a[min_c[i]][i]);
		return 0;
	}
	else if(i==4) printf("not found");
	return 0;
}