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
-1
我的代码:
#include<stdio.h> int main() { int M,N,i,j,k,p,min,put; int a[50][50]; while(scanf("%d%d",&M,&N)!=NULL) { put=0; for(i=0;i<M;i++) for(j=0;j<N;j++) scanf("%d",&a[i][j]); for(i=0;i<M;i++) { min=a[i][0]; for(j=1;j<N;j++) if(a[i][j]>min)min=a[i][j]; for(j=0;j<N;j++) if(a[i][j]==min) { k=j; p=0; while(p<M&&a[p][j]>=min) p++; if(p>=M) { printf("%d %d\n",i,k); put=1; } } } if(put==0) printf("-1\n"); } }
相关分类