【HUSTOJ】1092: 马鞍数

1092: 马鞍数

Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 402   Solved: 89 [ Submit][ Status][ Web Board]

Description

求一个n×m数阵中的马鞍数，输出它的位置。所谓马鞍数，是指在行上最小而在列上最大的数。如下： n=5 m=5  5 6 7 8 9  4 5 6 7 8  3 4 5 2 1  2 3 4 9 0  1 2 5 4 8  则1行1列上的数就是马鞍数。

Input

共n+1行，第一行： n m (n,m＜１０) 第2到n+1行：每行m个整数（每个数都＜１０）

Output

输出若干行：如果存在马鞍数，则输出所有马鞍数，每行一个，为行和列以及马鞍数。 如果不存在马鞍数，则输出'not exit'。

Sample Input

5 5 5 6 7 8 9 4 5 6 7 8 3 4 5 2 1 2 3 4 9 0 1 2 5 4 8

Sample Output

1 1 5 PS：maxn初始化时不能初始化为0，可能e[i][j]是负数

AC代码：

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int N = 100; const int inf = 0x3f3f3f3f; int n, m, k; int e[N][N], q1[N], q2[N], q3[N]; bool flag = true; void f(int a, int b, int c){ int minn = inf, maxn = -inf; //找出行最小的数 for(int i = 1; i <= m; i++){ minn = min(minn, e[a][i]); } //找出列最大的数 for(int i = 1; i <= n; i++){ maxn = max(maxn, e[i][b]); } //如果当前这个数等于行最小和列最大就加入 if(c == minn && c == maxn){ q1[k] = a; q2[k] = b; q3[k] = c; k++; flag = false; } } int main(){ k = 1; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> e[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ f(i, j, e[i][j]); } } int flag1 = true; for(int i = 1; i < k; i++){ if(flag1) flag1 = false; else printf("\n"); printf("%d %d %d", q1[i], q2[i], q3[i]); } if(flag) printf("not exit\n"); return 0; }