鞍点，二维数组、降维处理、列指针、行指针

PS：以下四种方法都是经过测试AC的，在格式上、运行上、结果上没有问题。但要问我具体的原理，我现在学的还不过关，讲不清楚

【问题描述】

找一个 n* n 的二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小（也可能没有鞍点，若有则仅有一个鞍点）。

请设计函数int Andian(int a[][30], int n)实现之，其中n代表二维数组的行列数，返回值为鞍点，若返回值为0则代表没有鞍点。

【输入形式】

二维数组的行数n，以及每一个数据元素值

【输出形式】

鞍点值或者NO，NO代表没有鞍点

【样例输入】

4

1 7 4 1

4 8 3 6

1 6 1 2

0 7 8 9

【样例输出】

6

【提示】

（1）请将函数定义为int Andian(int * p, int n)，那么调用语句为Andian( * a,n)，在该函数内部访问具体的数据时，应该用 * (p+i * n+j)的形式。p是列指针。

（2）或者将函数定义为int Andian(int (* p )[30], int n)，那么调用语句为Andian(a,n)，在该函数内部访问具体的数据时，可以用 * ( * (p+i)+j)的形式。p是行指针。

（3）请编写输入函数进行二维数组数据元素的录入：

void InputArray(int *p, int n);

1. 二维数组方法实现

#include <iostream>
using namespace std;
void InputArray(int a[][30], int n);//二维数组做参数声明时一定要声明列元素个数
int Andian(int a[][30], int n);

int main()
{
    int a[30][30], n, outcome;
    cin >> n;
    InputArray( a, n);//调用时，二维数组直接用数组名调用
    outcome = Andian( a,n);
    if( outcome ) cout << outcome << endl;
    else cout << "NO" << endl;
    return 0;
}

void InputArray(int a[][30], int n)//二维数组录入
{
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin >> a[i][j];
}

int Andian(int a[][30], int n)
{
    for(int i=0;i<n;++i)//先找每一行的最大值
    {
        int columnIndex=0,rowIndex=0;
        for(int j=columnIndex+1;j<n;++j)//固定行，找列
            if( a[i][j] > a[i][columnIndex] )
                columnIndex=j;//找到第i行的最大值在第columnIndex列

        for(int k=rowIndex+1;k<n;++k)//固定columnIndex列，再找行
            if( a[k][columnIndex] < a[rowIndex][columnIndex] )
                rowIndex=k;//找到第columnIndex列的最小值在第rowIndex行

        if( rowIndex == i )//如果columnIndex列的最小值所在的rowIndex行和大循环的第i行相等，则找到鞍点
            return a[rowIndex][columnIndex];//返回鞍点的值
    }
    return 0;
}

2. 数组降维方法实现

#include <iostream>
using namespace std;
void InputArray(int a[], int n);//做参数传递的时候把数组降维
int Andian(int a[], int n);

int main()
{
    int a[30][30], n, outcome;//定义的时候还是二维的数组
    cin >> n;
    InputArray( &a[0][0], n);//函数调用的时候传递第一个元素地址和每行或每列元素个数
    outcome = Andian( &a[0][0], n);
    if( outcome ) cout << outcome << endl;
    else cout << "NO" << endl;
    return 0;
}

void InputArray(int a[], int n)//降维录入
{
    for(int i=0;i<n*n;++i)//要实现全部数据的录入则循环要执行n*n次
        cin >> a[i];
}

int Andian(int a[], int n)
{
    for(int i=0;i<n;++i)//先找每一行的最大值
    {
        int columnIndex=0,rowIndex=0;
        for(int j=columnIndex+1;j<n;++j)//固定行，找列
            if( a[i*n+j] > a[i*n+columnIndex] )
                columnIndex=j;//找到第i行的最大值在第columnIndex列

        for(int k=rowIndex+1;k<n;++k)//固定columnIndex列，再找行
            if( a[k*n+columnIndex] < a[rowIndex*n+columnIndex] )
                rowIndex=k;//找到第columnIndex列的最小值在第rowIndex行

        if( rowIndex == i )//如果columnIndex列的最小值所在的rowIndex行和大循环的第i行相等，则找到鞍点
            return a[rowIndex*n+columnIndex];//返回鞍点的值
    }
    return 0;
}

3. 列指针方法实现

#include <iostream>
using namespace std;
void InputArray(int *p, int n);
int Andian(int *p, int n);

int main()
{
    int a[30][30], n, outcome;
    cin >> n;
    InputArray( *a, n);
    outcome = Andian( *a,n);
    if( outcome ) cout << outcome << endl;
    else cout << "NO" << endl;
    return 0;
}

void InputArray(int *p, int n)//二维数组录入
{
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin >> *(p+i*n+j);
}

int Andian(int *p, int n)
{
    for(int i=0;i<n;++i)//先找每一行的最大值
    {
        int columnIndex=0,rowIndex=0;
        for(int j=columnIndex+1;j<n;++j)//固定行，找列
            if( *(p+i*n+j) > *(p+i*n+columnIndex) )
                columnIndex=j;//找到第i行的最大值在第columnIndex列

        for(int k=rowIndex+1;k<n;++k)//固定columnIndex列，再找行
            if( *(p+k*n+columnIndex) < *(p+rowIndex*n+columnIndex) )
                rowIndex=k;//找到第columnIndex列的最小值在第rowIndex行

        if( rowIndex == i )//如果columnIndex列的最小值所在的rowIndex行和大循环的第i行相等，则找到鞍点
            return *(p+rowIndex*n+columnIndex);//返回鞍点的值
    }
    return 0;
}

4. 行指针方法实现

#include <iostream>
using namespace std;
void InputArray(int (*p)[30], int n);
int Andian(int (*p)[30], int n);

int main()
{
    int a[30][30], n, outcome;
    cin >> n;
    InputArray( a, n);
    outcome = Andian( a,n);
    if( outcome ) cout << outcome << endl;
    else cout << "NO" << endl;
    return 0;
}

void InputArray(int (*p)[30], int n)//二维数组录入
{
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin >> *(*(p+i)+j);
}

int Andian(int (*p)[30], int n)
{
    for(int i=0;i<n;++i)//先找每一行的最大值
    {
        int columnIndex=0,rowIndex=0;
        for(int j=columnIndex+1;j<n;++j)//固定行，找列
            if( *(*(p+i)+j) > *(*(p+i)+columnIndex) )
                columnIndex=j;//找到第i行的最大值在第columnIndex列

        for(int k=rowIndex+1;k<n;++k)//固定columnIndex列，再找行
            if( *(*(p+k)+columnIndex) < *(*(p+rowIndex)+columnIndex) )
                rowIndex=k;//找到第columnIndex列的最小值在第rowIndex行

        if( rowIndex == i )//如果columnIndex列的最小值所在的rowIndex行和大循环的第i行相等，则找到鞍点
            return *(*(p+rowIndex)+columnIndex);//返回鞍点的值
    }
    return 0;
}