• B2102 計算鞍點

計算鞍點

題目描述

給定一個 \(5 \times 5\) 的矩陣，每行只有一個最大值，每列只有一個最小值，尋找這個矩陣的鞍點。鞍點指的是矩陣中的一個元素，它是所在行的最大值，并且是所在列的最小值。

例如：在下面的例子中，第 \(4\) 行第 \(1\) 列的元素就是鞍點，值為 \(8\)。

11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25

輸入格式

輸入包含一個 \(5\) 行 \(5\) 列的矩陣。

輸出格式

如果存在鞍點，輸出鞍點所在的行、列及其值，如果不存在，輸出 not found。

樣例 #1

樣例輸入 #1

11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8  6 4 7 2
15 10 11 20 25

樣例輸出 #1

4 1 8

• 參考程序

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int a[N][N], b[N][N], n=5;

int main(){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) cin>>a[i][j];
    
//    找行最大 --- 找列數
    for(int i=1; i<=n; i++){
        int id = 1;
        for(int j=1; j<=n; j++)
            if(a[i][id] < a[i][j]) id = j;
        b[i][id] ++;
    } 
//    找列最小 ---  找行數 
    for(int j=1; j<=n; j++){
        int id = 1;
        for(int i=1; i<=n; i++)
            if(a[id][j] > a[i][j]) id = i;
        b[id][j] ++;
    } 
    int x,y;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            if(b[i][j] == 2){
                x=i,y=j;
            }
        }
    cout<<x<<" "<<y<<" "<<a[x][y]<<endl;
}