JOI 2017 Yo 5th

5.cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <cmath>
#include <cstring>
#include <map>
#include <set>
#include <utility>

using Pair = std::pair<int, int>;

int h, w;
int arr[1010][1010];
int dy[] = {0, 0, -1, 1}, dx[] = {1, -1, 0, 0};
std::vector<std::vector<std::set<Pair>>> check;

int main() {
    std::cin >> h >> w;

    std::map<int, Pair> pos;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            std::cin >> arr[i][j];

            pos.insert({arr[i][j], {i, j}});
        }
    }

    check.resize(h, std::vector<std::set<Pair>>(w));

    for(auto&& p : pos) {
        int y = p.second.first;
        int x = p.second.second;
        int q = p.first;
        
        for(int i = 0; i < 4; ++i) {
            int py = y + dy[i], px = x + dx[i];

            if(py < 0 || py >= h || px < 0 || px >= w)
                continue;

            if(q < arr[py][px]) {
                if(check[y][x].size() == 0) {
                    check[py][px].insert(p.second);
                }else {
                    for(auto&& r : check[y][x]) {
                        check[py][px].insert(r);
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            if(check[i][j].size() > 1) {
                ++ans;
            }
        }
    }

    std::cout << ans << std::endl;
}