Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-13

grafixMask

| 14:18

問題文, SRM 211

Algorithm Tutorials -- How to Find a Solutionから。

マスクしていない部分の面積。Flood fill。

351.71/500

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles) {
        const static int H = 400, W = 600;
        char canvas[H][W];
        memset(canvas, ' ', H*W);
        for (int i = 0; i < rectangles.size(); i++) {
            int r0, c0, r1, c1;
            sscanf(rectangles[i].c_str(), "%d %d %d %d", &r0, &c0, &r1, &c1);
            for (int r = r0; r <= r1; r++)
                for (int c = c0; c <= c1; c++)
                    canvas[r][c] = '#';
        }

        vector<int> areas;
        for (int r = 0; r < H; r++)
            for (int c = 0; c < W; c++) {
                if (canvas[r][c] == '#') continue;
                canvas[r][c] = '#';
                int area = 1;
                queue<pair<int,int> > Q;
                Q.push(make_pair(r, c));
                while (!Q.empty()) {
                    pair<int,int> p(Q.front()); Q.pop();
                    for (int i = 0; i < 4; i++) {
                        const static int d[4][2] = {
                            {1,0}, {-1,0}, {0,1}, {0,-1} };
                        const int nr = p.first + d[i][0];
                        const int nc = p.second + d[i][1];
                        if (0<=nr&&nr<H && 0<=nc&&nc<W && canvas[nr][nc] != '#') {
                            canvas[nr][nc] = '#';
                            Q.push(make_pair(nr,nc));
                            area++;
                        }
                    }
                }
                areas.push_back(area);
            }
        sort(areas.begin(), areas.end());
        return areas;
    }
};