【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

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;
}