Ето я и втората задача за двумерни масиви:
Задача 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. Нямаме го по условие, но извеждаме и коя е самата точка – координатите и стойността ѝ.
За същия ред намираме и минималната стойност. Постъпваме по същия начин, както търсейки комбинация макс-мин, но на мушката ни този път е мин-макс.
Както и в миналия пример, любителите на кратките описания тук също могат да опишат двете действия в едно.