287 马鞍点-Toy模板网

这篇具有很好参考价值的文章主要介绍了287 马鞍点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目2：求矩阵中的马鞍点

问题描述

所设计的程序能够通过编译。若矩阵中的某个元素是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。编写程序求出矩阵中的所有马鞍点。

输入格式

首先输入两个整数n和m，为矩阵维数，然后输入矩阵的值。

输出格式

输出矩阵中的所有马鞍点，输出顺序：行序优先，按行、列序号递增顺序输出。

，若有多个马鞍点，每个马鞍点一行。也可能没有马鞍点，则输出NO。

样例输入

4 4

2 7 9 10

1 0 7 12

8 23 13 15

4 6 12 18

样例输出

3 1 8

思路/分析：

1、比较第i行中所有元素，找到第一个最小值a[i][j]（可能不止一个）。验证它是否是j列最大的，如果是的话输出；如果不是的话，找到第二个，验证其是否是当列最大的。直到第i行的最小值全部被遍历完。

2、遍历i行。

实操：设置了两个辅助数组，用来记录每行或每列的最大或最小值。果然方便了很多

（依稀记得今年1月做过这个题，也是这个想法。但是过年在老家电脑好像出了问题没做出来哎

注意点：第一次交上去五十，因为忘记了输出NO的情况。

 1 #include<stdio.h>
 2 #include<bits/stdc++.h>
 3 
 4 int main()
 5 {
 6     int n,m;
 7     scanf("%d %d",&n,&m);
 8     
 9     int array[n][m];
10     int flag=0;//judge whether the dot exists
11     int i,j;
12     int imin[n]={0},jmax[m]={0};//assist-array,record the max/min
13     
14     
15     for(i=0;i<n;i++)
16     {
17         for(j=0;j<m;j++)
18         {
19             scanf("%d",&array[i][j]);
20             if(j==0) imin[i]=array[i][j];
21             
22             if(imin[i]>array[i][j]) imin[i]=array[i][j];
23             if(jmax[j]<array[i][j]) jmax[j]=array[i][j];
24         }
25     }
26     
27     for(i=0;i<n;i++)
28     {
29         for(j=0;j<m;j++)
30         {
31             if(array[i][j]==imin[i]&&array[i][j]==jmax[j])
32             {
33                 flag=1;
34                 printf("%d %d %d\n",i+1,j+1,array[i][j]);
35             }
36         }
37     }
38     if(flag==0) printf("NO\n");
39     return 0;
40 }