C语言 每日一题 PTA 10.25 day4

语言 每日一题 PTA 10.25 day4"/>

C语言 每日一题 PTA 10.25 day4

10.25
求解马鞍点问题
若矩阵Anm中某个元素A[i][j]是矩阵第i行中值最小的元素，同时又是第j列中值最大的元素，则称元素A[i][j]是矩阵中的一个马鞍点。
设以二维数组存储矩阵，编写算法求矩阵A中的所有马鞍点，算法的时间复杂度要尽量的低。
注意当最大值（最小值）并列相等时，会出现多鞍点的情况。
输入格式 :
第一行输入矩阵的总行数M和总列数N，以空格间隔。
之后的M行，依次输入矩阵的各行数据，以空格间隔。
输出格式 :若有马鞍点，则以行序为主序，依次输出各个马鞍点。
每个马鞍点以（row, col, val）的形式输出，其中row 代表马鞍点的行号，col代表马鞍点的列号，val代表马鞍点的值。
若无马鞍点，则输出“NONE”。

#include <stdio.h>
#define Mmax 100
#define Nmax 100int main()
{int M, N;int i, j, k, b = 0, min, t = 0;int A[Mmax][Nmax];int B[Nmax];scanf("%d %d", &M, &N);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];B[t] = 0;t++;for (j = 1; j < N; j++){if (A[i][j] < min){min = A[i][j];t = 0;B[t] = j;t++;}else if (A[i][j] == min){B[t] = j;t++;}}for (k = 0; k < t; k++){int y, l = 0;int x = B[k];for (y = 0; y < M; y++){if (min < A[y][x]){l = 1;}}if (l == 0){printf("(%d,%d,%d)", i + 1, x + 1, min);b = -1;}}}if (b != -1){printf("NONE");}
}

运行结果：