求解马鞍点

问题 C: DS-5.3 求解马鞍点问题(by Yan)时间限制: 1 Sec 内存限制: 128 MB 提交: 474 解决: 170 [提交] [状态] [讨论版] [命题人:zengyan]

题目描述 若矩阵An*m中某个元素A[i][j]是矩阵第i行中值最小的元素，同时又是第j列中值最 大的元素，则称元素A[i][j]是矩阵中的一个马鞍点。设以二维数组存储矩阵，编写 算法求矩阵A中的所有马鞍点，算法的时间复杂度要尽量的低。

注意当最大值（最小值）并列相等时，会出现多鞍点的情况。

#include<stdio.h> #include<stdlib.h> int main() { int n, m; int count = 0; int num[10] = {0}; int a[100][100]; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } for (int i = 1; i <= n; i++) { int flag = 0; int k = 0; int min = a[i][1]; num[k++] = 0; for (int j = 2; j <= m; j++) { if (min == a[i][j]) { num[k++] = j; } else if (min > a[i][j]) { k = 0; min = a[i][j]; num[k++] = j; } } int p = 0; for (p = 0; p < k; p++) { flag = 0; int q; for (q = 1; q <= n; q++) { if (a[q][num[p]] > min) { flag = 1; break; } } if (q > n) { if (flag == 0) { count++; //注意定义i在括号外面 //这样就不用重新定义数组去记住元素的行下标了 //直接使用上面的i就行 //它已经循环到了目标元素的行下标地方 printf("(%d,%d,%d)", i, num[p], a[i][num[p]]); } } } } if (count == 0) { printf("NONE"); } return 0; }