#include #include #include #include #include #include #include #include using namespace std; ifstream inF("prominence2d.in"); ofstream outF("prominence2d.out"); #define cin inF #define cout outF const int MAX_NM = 510; int n, m; int h[MAX_NM][MAX_NM]; int rel[MAX_NM][MAX_NM]; bool isPeak[MAX_NM][MAX_NM]; void input() { cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> h[i][j]; } } } void output() { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (isPeak[i][j]) cout << rel[i][j] << "\n"; } } } struct Node { int h; int i, j; }; bool operator<(const Node& a, const Node& b) { return a.h > b.h; } vector nodes; struct Pos { int i, j; }; bool operator==(const Pos& a, const Pos& b) { return a.i == b.i && a.j == b.j; } Pos par[MAX_NM][MAX_NM]; Pos findRoot(Pos a) { Pos& p = par[a.i][a.j]; if (p == a) return a; return p = findRoot(p); } void unite(Pos a, Pos b, int currH) { a = findRoot(a); b = findRoot(b); if (h[a.i][a.j] > h[b.i][b.j]) { rel[b.i][b.j] = h[b.i][b.j] - currH; par[b.i][b.j] = a; } else { rel[a.i][a.j] = h[a.i][a.j] - currH; par[a.i][a.j] = b; } } void solve() { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { isPeak[i][j] = true; if (i > 0 && h[i - 1][j] > h[i][j]) isPeak[i][j] = false; else if (i < n - 1 && h[i + 1][j] > h[i][j]) isPeak[i][j] = false; else if (j > 0 && h[i][j - 1] > h[i][j]) isPeak[i][j] = false; else if (j < m - 1 && h[i][j + 1] > h[i][j]) isPeak[i][j] = false; nodes.push_back({h[i][j], i, j}); par[i][j] = {i, j}; } } std::sort(nodes.begin(), nodes.end()); for (const Node& node : nodes) { int i = node.i; int j = node.j; if (i > 0 && h[i - 1][j] > h[i][j]) unite({i, j}, {i - 1, j}, node.h); if (i < n - 1 && h[i + 1][j] > h[i][j]) unite({i, j}, {i + 1, j}, node.h); if (j > 0 && h[i][j - 1] > h[i][j]) unite({i, j}, {i, j - 1}, node.h); if (j < m - 1 && h[i][j + 1] > h[i][j]) unite({i, j}, {i, j + 1}, node.h); } Pos peak = findRoot({0, 0}); rel[peak.i][peak.j] = h[peak.i][peak.j]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); { input(); solve(); output(); } return 0; }