/*========================================================================
计算鞍点
总时间限制: 1000ms 内存限制: 65536kB
描述
输入一个二维 (5*5)数组，每行只有一个最大值，每列只有一个最小值。
如果存在鞍点，则输出鞍点所在的位置（行和列），不存在鞍点时，要输出“not found”。
鞍点指的是数组中的一个元素，它是所在行的最大值，并且是所在列的最小值。
例如：在下面的例子中（第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
==========================================================================*/
#include<stdio.h>
#define maxN 50
#define maxM 50
int main()
{
int n,m,i,j,k;
int a[maxN][maxM]={0};
int max,x,y;
int flag;
freopen("5.in","r",stdin);
n=5;
m=5;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<n;i++)
{
max=a[i][0];//假定行的第一个元素是该行最大值
x=i;//记录最大值所在的行列坐标
y=0;
for(j=1;j<m;j++)//寻找行的最大值
{
if(a[i][j]>max)
{
max=a[i][j];
y=j;
}
}
flag=1;
for(k=0;k<n;k++)//检测刚刚找到行最大值max是否是其所在的第y列的最小值
{
if(a[k][y]<max)
{
flag=0;//flag为0表示max不是第y列的最小值
break;
}
}
if(flag==1)//flag为1表示max是第y列的最小值，即找到了鞍点，可以输出了
{
printf("%d %d %d\n",x+1,y+1,max);
break;//最多只有一个鞍点，所以可以结束查找鞍点的工作了
}
}
if(flag==0)//假如刚才没找到鞍点，说明该数组不存在鞍点。
printf("not found\n");
return 0;
}
1 #include <stdio.h>
2 #define maxN 5
3 struct obj
4 {
5 int maxOrMinNumber;
6 int index;
7 };
8 int main(int argc, char *argv[])
9 {
10 int n=maxN,i,j,t;
11 struct obj rowMaxIndex[maxN];
12 struct obj colMinIndex[maxN];
13 int k,flag;
14
15 for(i=0;i<maxN;i++)
16 {
17 rowMaxIndex[i].index=0;
18 colMinIndex[i].index=0;
19 }
20 for(i=0;i<maxN;i++)
21 {
22 for(j=0;j<maxN;j++)
23 {
24 scanf("%d",&t); //输入a[i][j]
25 if(j==0) // 更新第i行最大值和最大值所在列下标
26 {
27 rowMaxIndex[i].maxOrMinNumber=t;
28 rowMaxIndex[i].index=0;
29 }
30 else if(t>rowMaxIndex[i].maxOrMinNumber)
31 {
32 rowMaxIndex[i].maxOrMinNumber=t;
33 rowMaxIndex[i].index=j;
34 }
35
36 if(i==0)//更新第j列最小值和最小值所在行的下标
37 {
38 colMinIndex[j].maxOrMinNumber=t;
39 colMinIndex[j].index=0;
40 }
41 else if(t<colMinIndex[j].maxOrMinNumber)
42 {
43 colMinIndex[j].maxOrMinNumber=t;
44 colMinIndex[j].index=i;
45 }
46 }
47 }
48
49 flag=0;
50 for(i=0;i<maxN;i++)
51 {
52 k=rowMaxIndex[i].index;//第i行最大值的列下标
53 if(colMinIndex[k].index==i)
54 {
55 printf("%d %d %d\n",i+1,k+1,rowMaxIndex[i].maxOrMinNumber);
56 flag=1;
57 break;
58 }
59 }
60 if(flag==0) printf("not found\n");
61 return 0;
62 }
View Code
