Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-10-12

TopographicalImage

| 19:19

問題文, SRM 210

Algorithm Tutorials -- Planning an Approach to a TopCoder Problem: Section 2から。

各頂上から上らずに到達することができる地点の数を数える。ただし、同じ地点は数えない。

390.67/1000

class TopographicalImage {
public:
    vector <int> calcPeakAreas(vector <string> topoData) {
        H = topoData.size();
        W = topoData[0].size();
        result.clear();
        while (true) {
            int mx=0, my=0;
            char mh=0;
            for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++) {
                    if (topoData[y][x] != VISITED && topoData[y][x] > mh) {
                        my = y;
                        mx = x;
                        mh = topoData[y][x];
                    }
                }
            if (mh == 0) break;
            result.push_back(0);
            visit(my, mx, mh, topoData);
        }
        return result;
    }
private:
    const static char VISITED = 127;
    int H, W;
    vector <int> result;
    void visit(const int py, const int px, const char ph, 
            vector<string>& topoData) {
        result.back()++;
        topoData[py][px] = VISITED;
        for (int dy = -1; dy <= 1; dy++)
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == 0 && dx == 0) continue;
                const int ny = py + dy;
                const int nx = px + dx;
                if (0<=ny&&ny<H && 0<=nx&&nx<W) {
                    const int nh = topoData[ny][nx];
                    if (nh <= ph)
                        visit(ny, nx, nh, topoData);
                }
            }
    }
};