Description
给定一个海拔平面图,相当于一个二维数组,数组的每个元素表示一个点的海拔高度。请判断该图中是否存在鞍点,如果存在,则输出该鞍点的位置,即行、列坐标。
本题规定鞍点的定义为:该点的值在它所在的那行中是唯一最大的,且该点的值在它所在的那列中是唯一最小的。
Input
输入有多个测试用例,如果把每个测试用例看作一个"块",那么,在一个"块"中:
第一行是两个正整数m和n,分别表示该平面图的行数和列数。0 < m, n ≤ 1000
接下来m行,每行n个非负整数,每个整数表示一个点的海拔高度。
测试数据保证如果存在鞍点,则只存在一个鞍点。
Output
对每个测试用例输出一行:如果该图存在鞍点,则输出该鞍点的行、列坐标。否则输出 -1
Sample Input
5 6
75 99 47 95 17 69
80 5 2 97 66 8
38 32 40 89 50 66
48 44 21 66 23 10
11 21 6 74 6 55
4 4
5 4 5 3
9 8 7 8
3 2 6 1
4 4 3 3
Sample Output
3 3
#include<stdio.h>
int main(void){
int m, n, i, j, sum, c, max, min, xia1, xia2, d;
static int z[1005][1005];
static int jie[1005][1005]={-1, -1, -1};
static int jie2[1005][1005]={-1, -1, -1};
while(scanf("%d%d", &m, &n)!=EOF){
for(i=1; i<=1003; i++)
for(j=1; j<=1003; j++){
jie[i][j]=-1;
jie2[i][j]=-1;
}
for(i=1; i<=m; i++)
for(j=1; j<=n; j++)
scanf("%d", &z[i][j]); //读入矩阵
for(i=1; i<=m; i++){
max=-9999; c=0;
for(j=1; j<=n; j++)
if(z[i][j]>=max)
{ max=z[i][j]; xia1=i; xia2=j;}
for(j=1; j<=n; j++)
if(z[i][j]==max) c++;
if(c==1) jie[xia1][xia2]=z[xia1][xia2];
} //横向求最大项并作筛子jie记录
for(j=1; j<=n; j++){
min=9999; c=0;
for(i=1; i<=m; i++)
if(z[i][j]<=min)
{ min=z[i][j]; xia1=i; xia2=j;}
for(i=1; i<=m; i++)
if(z[i][j]==min) c++;
if(c==1) jie2[xia1][xia2]=z[xia1][xia2];
} //纵向求最xiao项并作筛子jie2记录
d=0;
for(i=1; i<=m; i++)
for(j=1; j<=n; j++){
if(jie[i][j]==jie2[i][j]&&jie[i][j]!=-1&&jie2[i][j]!=-1)
{ printf("%d %d\n", i-1, j-1); d++; break; }
if(d>0) break;
} //两个筛子进行对比输出
if(d==0) printf("-1\n");
}
return 0;
}
```
个人思路: 因为使用原始算法超时不通过, 所以改进思路: 定义jie和jie2两个和题目矩阵一样的二维数组(全部元素-1), 把每一行唯一最大的元素记录如z[5][6
然后把jie[5][6]修改为那个值, 每一列同理jie2中,最后扫描整个jie和jie2,若两者相同且不为-1, 则项为鞍点。 求大神指点
oj系统不但使用所列出的测试用例测试程序,还使用一些别的没有列出的用例。你多测试下,看看是不是有用例不通过。
以前做过该类程序,建议使用微积分2次积分思想解决该问题