Двумерни масиви – седлова точка

Ето я и втората задача за двумерни масиви:

Задача 2: Да се преброят седловите точки на двумерен масив. Седлова точка се нарича елемент, който едновременно е минимален за реда и максимален за стълба, в който се намира, или обратното.

Решение:

#include <iostream>
#include <iostream>
#define ARRA 4
#define ARRB 4
using namespace std;

int main(){

    int arr[ARRA][ARRB];
    int row, r, col, m;

    int br = 0;

    bool fail = false;

	// Въвеждаме масива
    cout << "Въведете двумерен масив (" << ARRA << " на " << ARRB << "):\n";
    for(row=0; row<ARRA; row++)
        for(col=0; col<ARRB; col++){
        cin >> arr[row][col];
    }
    cout << "[Готово]\n" << endl;

    cout << "Намерих следните седлови точки: ";

	// Обхождаме матрицата ред по ред
    for(row=0; row<ARRA; row++){
        m = 0;

	  // Намираме максимална точка за реда
        for(col=0; col<ARRB; col++){
            if(arr[row][col] > arr[row][m])
                m = col;
        }
        fail = false;
      // Проверяваме минимална ли е тя за колоната
        for(r=0; r<ARRA; r++){
            if(arr[r][m] < arr[row][m]) fail = true;
        }
      // Намерили ли сме седлова точка?
        if(!fail){
            br++;
            cout << " (" << row+1 << "," << m+1 << ") стойност=" << arr[row][m];
        }

        m = 0;
      // Намираме минимална точка за реда
        for(col=0; col<ARRB; col++){
            if(arr[row][col] < arr[row][m])
            m = col;
        }
        fail = false;
      // Проверяваме максимална ли е тя за колоната
        for(r=0; r<ARRA; r++){
            if(arr[r][m] > arr[row][m]) fail = true;
        }
      // Намерили ли сме седлова точка?
        if(!fail){
            br++;
            cout << " (" << row+1 << "," << m+1 << ") стойност=" << arr[row][m];
        }

    }

    cout << "\n" << br << " общо";
    return 0;
}

Каква е логиката:

  • За всеки ред (27) откриваме максимална стойност (31-34). Отбелязваме не каква е, а къде е (реда го знаем, записваме колоната), използвайки променливата m (33).
  • Проверяваме дали този максимален елемент се явява минимален в m-тата колона (37-39) и ако  това не е така, fail става истина (33).
  • Ако сме намерили седлова точка (обходили сме всички колони, а fail си е останала лъжа), увеличаваме брояча br с 1. Нямаме го по условие, но извеждаме и коя е самата точка – координатите и стойността ѝ.

За същия ред намираме и минималната стойност. Постъпваме по същия начин, както търсейки комбинация макс-мин, но на мушката ни този път е мин-макс.

Както и в миналия пример, любителите на кратките описания тук също могат да опишат двете действия в едно.

Leave a comment

Your email address will not be published. Required fields are marked *