Задача Олимпиадная(Штурм)

Question

   #include <iostream>

using namespace std;

int main()
{
    int n, m, p = 0, max = 0;
    cin >> n >> m;
    int** a = new int* [n];
    for (int i = 0; i < n;i++)
    {
        a[i] = new int[m];
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    }
    
    max = a[0][0];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if(max <= a[i][j])
                max = a[i][j];
    
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if(a[i][j] == max)
                p++;
            
    }
    cout << p;
}

Вот мое решение проходит четыре теста

Answer 1

Это решение находит только клетки с максимальным по карте количеством, а нужны локальные максимумы. Для их нахождения достаточно для каждой клетки проверить четырёх (если они есть) соседей.

if (a[i][j] > a[i-1][j] && a[i][j] > a[i][j-1] &&
    a[i][j] > a[i+1][j] && a[i][j] > a[i][j+1]) ...

Для исключения особых случаев на краях можно сделать расширенную матрицу, заполнив фиктивные ряды нулями.

Answer 2

Вы смотрите, сколько ячеек с максимальным (по всей матрице) значением, в то время как требуется только локальный максимум - больше, чем в соседних! Что-то типа

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;

int ok(const vector<vector<int>>& v, int i, int j)
{
    if (i-1 >= 0 && v[i-1][j] >= v[i][j]) return 0;
    if (i+1 < v.size() && v[i+1][j] >= v[i][j]) return 0;
    if (j-1 >= 0 && v[i][j-1] >= v[i][j]) return 0;
    if (j+1 < v[i].size() && v[i][j+1] >= v[i][j]) return 0;
    return 1;
}

int main(int argc, const char * argv[])
{
    int n, m, sum = 0;
    cin >> n >> m;
    vector<vector<int>> v(n,vector<int>(m));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> v[i][j];

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            sum += ok(v,i,j);
    cout << sum << endl;
}

Однопроходный алгоритм, раз уж Yaroslav так требует, но сам не делает:

int main()
{
    int n,m, sum = 0;
    cin >> n >> m;
    pair<int,int> * a = new pair<int,int>[m+2]{{0,0}};
    for(int i = 0; i <= n; ++i)
    {
        for(int j = 1; j <= m+1; ++j)
        {
            int x = 0;
            if (i < n && j <= m) cin >> x;

            if (x < a[j].first && a[j].second) sum++;

            a[j].second = false;
            if (a[j].first < x) a[j].second = true;
            a[j].first = x;

            if (x <= a[j-1].first) a[j].second = false;
            if (x >= a[j-1].first) a[j-1].second = false;

        }
    }
    cout << sum;
}

На случай, если решение с pair тоже на уровне ЕГЭ :), вот решение с простым int'ом:

int main()
{
    int n,m, sum = 0;
    cin >> n >> m;
    int * a = new int[m+2]{0};
    for(int i = 0; i <= n; ++i)
    {
        for(int j = 1; j <= m+1; ++j)
        {
            int x = 0;
            if (i < n && j <= m) cin >> x;

            if (x < (a[j]&~0x80) && (a[j]&0x80)) sum++;

            if ((a[j]&~0x80) < x) a[j] = x | 0x80; else a[j] = x;

            if (x <= (a[j-1]&~0x80)) a[j] &= ~0x80;
            if (x >= (a[j-1]&~0x80)) a[j-1] &= ~0x80;

        }
    }
    cout << sum;
}

"Магическую константу" 0x80 можно заменить на другую, типа, 0x10000 - просто раз значения в матрице не превышают ста, и это значение годится...

Все решения проверены здесь: https://ipc.susu.ru/28620.html

БЛОГ НА HUSL

Задача Олимпиадная(Штурм)

Ответы (2 шт):