Create your Gitee Account
Explore and code with more than 6 million developers,Free private repositories !:)
Sign up
Clone or download
EX7_2:鞍点.md 2.32 KB
Copy Edit Web IDE Raw Blame History
徒步天下 authored 2017-11-07 10:08 . 新建 EX7_2:鞍点.md

EX7_2:鞍点

题目内容:

给定一个n*n矩阵A。矩阵A的鞍点是一个位置(i,j),在该位置上的元素是第i行上的最大数,第j列上的最小数。一个矩阵A也可能没有鞍点。 你的任务是找出A的鞍点。

输入格式:

输入的第1行是一个正整数n, (1<=n<=100),然后有n行,每一行有n个整数,同一行上两个整数之间有一个或多个空格。

输出格式:

对输入的矩阵,如果找到鞍点,就输出其下标。下标为两个数字,第一个数字是行号,第二个数字是列号,均从0开始计数。

如果找不到,就输出

NO

题目所给的数据保证了不会出现多个鞍点。

输入样例:

4 
1 7 4 1 
4 8 3 6 
1 6 1 2 
0 7 8 9

输出样例:

2 1

时间限制:500ms内存限制:32000kb

题解

#include <stdio.h>

int a[101][101];

// 读入矩阵
int readMaxtrix(int a[][101], int n)
{
    // 保留0行,0列
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            scanf("%d", &a[i][j]);
    return 0;
}

int saddle(int a[][101], int n)
{
    int found=0;
    // 将每一行的最大数放到0列
    for (int i=1; i<=n; ++i)
    {
        int maxValue=a[i][1], maxRow=1;
        for (int j=2; j<=n; ++j)
            if (a[i][j]>maxValue)
            {
                maxValue = a[i][j];
                maxRow = j;
            }
        a[i][0] = maxRow;
    }
     // 将每一列的最小数放到0行
    for (int j=1; j<=n; ++j)
    {
        int minValue=a[1][j], minCol=1;
        for (int i=2; i<=n; ++i)
            if (a[i][j]<minValue)
            {
                minValue = a[i][j];
                minCol = i;
            }
        a[0][j] = minCol;
    }
    // 查找鞍点
    for (int i=1; i<=n; ++i)
        if (a[0][a[i][0]]==i)
        {
            found=1;
            printf("%d %d\n", i-1, a[i][0]-1);
        }
    return found;
}

int printMaxtrix(int a[][101], int n)
{
    for (int i=0;i<=n;i++)
    {
        for (int j=0; j<n; j++)
            printf("%d ", a[i][j]);
        printf("%d\n", a[i][n]);
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);
    readMaxtrix(a, n);
    if (!saddle(a, n))
        printf("NO\n");
    return 0;
}

Comment ( 0 )

Sign in for post a comment