第16回日本情報オリンピック予選 E. 尾根(Ridge)

第16回日本情報オリンピック予選 E. 尾根(Ridge)

E: 尾根 (Ridge) - 第１６回日本情報オリンピック 予選（オンライン） | AtCoder

感想

典型的なdfsに落とし込む問題

解法

水が流れる方向に沿って、辺を張る。このとき、出次数が0であるような頂点がそれ以降どこにも水が流れない「谷」である。ある頂点が尾根であるための必要十分条件は、その頂点からスタートして、2つ以上の異なる谷に到達可能であることである。よって、各頂点からdfsをして、そこから到達可能な点が一つならば、その頂点の番号を記録し、2つ以上ある場合はINFなどと記録しておくようなdpで解くことができる。$\ O(hw)\ $。

実装

#include "bits/stdc++.h"
using namespace std;

static const int INF = 0x3f3f3f3f;

vector<int> g[1010101];
bool used[1010101];
int dest[1010101];
int h, w;

void add(int fromy, int fromx, int toy, int tox) {
        g[fromy * w + fromx].push_back(toy * w + tox);
}

void dfs(int v) {
        used[v] = true;
        if (g[v].size() == 0) {
                dest[v] = v;
                return;
        }
        set<int> can;
        for (auto u : g[v]) {
                if (!used[u]) dfs(u);
                can.insert(dest[u]);
        }
        if (can.size() > 1) dest[v] = INF;
        else for (auto c : can) dest[v] = c;
        return;

}

void solve() {
        cin >> h >> w;
        vector<vector<int> > s(h, vector<int> (w));
        for (int y = 0; y < h; y ++) {
                for (int x = 0; x < w; x ++) {
                        cin >> s[y][x];
                }
        }
        for (int y = 0; y < h; y ++) {
                for (int x = 0; x < w - 1; x ++) {
                        if (s[y][x] < s[y][x + 1]) add(y, x + 1, y, x);
                        else add(y, x, y, x + 1);
                }
        }
        for (int x = 0; x < w; x ++) {
                for (int y = 0; y < h - 1; y ++) {
                        if (s[y][x] < s[y + 1][x]) add(y + 1, x, y, x);
                        else add(y, x, y + 1, x);
                }
        }
        for (int i = 0; i < h * w; i ++) if (!used[i]) dfs(i);
        int ans = 0;
        for (int i = 0; i < h * w; i ++) ans += dest[i] == INF;
        cout << ans << endl;
        return;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}