qq_32653757 2015-11-21 12:26 采纳率: 76.9%
浏览 3108
已结题

C语言,寻找二维数组鞍点,代码个人测试正确, 但是wrong answer, 求大神指点

Description
给定一个海拔平面图,相当于一个二维数组,数组的每个元素表示一个点的海拔高度。请判断该图中是否存在鞍点,如果存在,则输出该鞍点的位置,即行、列坐标。

本题规定鞍点的定义为:该点的值在它所在的那行中是唯一最大的,且该点的值在它所在的那列中是唯一最小的。

Input
输入有多个测试用例,如果把每个测试用例看作一个"块",那么,在一个"块"中:

第一行是两个正整数m和n,分别表示该平面图的行数和列数。0 < m, n ≤ 1000

接下来m行,每行n个非负整数,每个整数表示一个点的海拔高度。

测试数据保证如果存在鞍点,则只存在一个鞍点。

Output
对每个测试用例输出一行:如果该图存在鞍点,则输出该鞍点的行、列坐标。否则输出 -1

Sample Input
5 6
75 99 47 95 17 69
80 5 2 97 66 8
38 32 40 89 50 66
48 44 21 66 23 10
11 21 6 74 6 55
4 4
5 4 5 3
9 8 7 8
3 2 6 1
4 4 3 3

Sample Output
3 3

-1

    #include<stdio.h>
    int main(void){
    int m, n, i, j, sum, c, max, min, xia1, xia2, d;
    static int z[1005][1005];
    static int jie[1005][1005]={-1, -1, -1};
    static int jie2[1005][1005]={-1, -1, -1};
    while(scanf("%d%d", &m, &n)!=EOF){
    for(i=1; i<=1003; i++)
    for(j=1; j<=1003; j++){
    jie[i][j]=-1;
    jie2[i][j]=-1;
    }


    for(i=1; i<=m; i++)
    for(j=1; j<=n; j++)
    scanf("%d", &z[i][j]);                 //读入矩阵

    for(i=1; i<=m; i++){
    max=-9999; c=0;
    for(j=1; j<=n; j++)
    if(z[i][j]>=max)
    { max=z[i][j]; xia1=i; xia2=j;}
    for(j=1; j<=n; j++)
    if(z[i][j]==max) c++;
      if(c==1) jie[xia1][xia2]=z[xia1][xia2];
    }                                           //横向求最大项并作筛子jie记录

    for(j=1; j<=n; j++){
    min=9999;  c=0;
    for(i=1; i<=m; i++)
    if(z[i][j]<=min)
    { min=z[i][j]; xia1=i; xia2=j;}
    for(i=1; i<=m; i++)
    if(z[i][j]==min) c++;
    if(c==1)    jie2[xia1][xia2]=z[xia1][xia2];
    }                                                 //纵向求最xiao项并作筛子jie2记录

    d=0;
    for(i=1; i<=m; i++)
    for(j=1; j<=n; j++){
    if(jie[i][j]==jie2[i][j]&&jie[i][j]!=-1&&jie2[i][j]!=-1)
    {   printf("%d %d\n", i-1, j-1);   d++;     break;  }
    if(d>0) break;
    }                                                       //两个筛子进行对比输出

    if(d==0) printf("-1\n");
    }
    return 0;
    }
    ```
个人思路:   因为使用原始算法超时不通过,   所以改进思路: 定义jie和jie2两个和题目矩阵一样的二维数组(全部元素-1),   把每一行唯一最大的元素记录如z[5][6
然后把jie[5][6]修改为那个值,   每一列同理jie2中,最后扫描整个jie和jie2,若两者相同且不为-1,    则项为鞍点。       求大神指点
  • 写回答

2条回答 默认 最新

  • threenewbee 2015-11-21 15:19
    关注

    oj系统不但使用所列出的测试用例测试程序,还使用一些别的没有列出的用例。你多测试下,看看是不是有用例不通过。

    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名