TOP HSGTPHCM L9 2016-2017

#define task "TOP"

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e2 + 5;
int n, m, h[N][N];
int vis[N][N], mark; // Mảng đánh dấu
bool OnTop[N][N];

void Read()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> h[i][j];
}

bool BFS(int x, int y) // Các ô có thể đến được từ ô (x, y) mà không cần "đi xuống"
{
    queue<pair<int, int>> q;
    q.emplace(x, y);
    ++mark; // Ta sử dụng kĩ thuật đánh dấu bằng số nguyên để tránh việc phải khởi tạo lại mảng đánh dấu

    vis[x][y] = mark;

    while (!q.empty())
    {
        pair<int, int> c = q.front();
        q.pop();

        if (h[c.first][c.second] > h[x][y]) // Có thể "đi lên" ô cao hơn
            return true;

        for (int i = -1; i <= 1; ++i)
            for (int j = -1; j <= 1; ++j)
            {
                int u = c.first + i,
                    v = c.second + j;

                if (u > 0 && u <= n && v > 0 && v <= m) // Ô này vẫn nằm trong đồn điền nhà Tý
                    if (h[u][v] >= h[x][y] && vis[u][v] != mark)
                    {
                        vis[u][v] = mark;
                        q.emplace(u, v);
                    }
            }
    }

    return false;
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            OnTop[i][j] = !BFS(i, j); // Không thể đến được ô cao hơn mà không "đi xuống"

    int ans(0);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (OnTop[i][j])
            {
                if (OnTop[i - 1][j - 1] || OnTop[i - 1][j] || OnTop[i - 1][j + 1] || OnTop[i][j - 1])
                    ;
                else
                    ++ans;
            }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}