Problem Statement

In one mode of the grafix software package, the user blocks off portions of a masking layer using opaque rectangles. The bitmap used as the masking layer is 400 pixels tall and 600 pixels wide. Once the rectangles have been blocked off, the user can perform painting actions through the remaining areas of the masking layer, known as holes. To be precise, each hole is a maximal collection of contiguous pixels that are not covered by any of the opaque rectangles. Two pixels are contiguous if they share an edge, and contiguity is transitive.

You are given a named rectangles, the elements of which specify the rectangles that have been blocked off in the masking layer. Each in rectangles consists of four integers separated by single spaces, with no additional spaces in the string. The first two integers are the window coordinates of the top left pixel in the given rectangle, and the last two integers are the window coordinates of its bottom right pixel. The window coordinates of a pixel are a pair of integers specifying the row number and column number of the pixel, in that order. Rows are numbered from top to bottom, starting with 0 and ending with 399. Columns are numbered from left to right, starting with 0 and ending with 599. Every pixel within and along the border of the rectangle defined by these opposing corners is blocked off.

Return a containing the area, in pixels, of every hole in the resulting masking area, sorted from smallest area to greatest.

Definition

Class:grafixMask

Method:sortedAreas

Parameters:vector <string>

Returns:vector <int>

Method signature:vector <int> sortedAreas(vector <string> rectangles)

Limits

Time limit (s):840.000

Memory limit (MB):64

Notes

  • Window coordinates are not the same as Cartesian coordinates. Follow the definition given in the second paragraph of the problem statement.

Constraints

  • rectangles contains between 1 and 50 elements, inclusive
  • each element of rectangles has the form “ROW COL ROW COL”, where: “ROW” is a placeholder for a non-zero-padded integer between 0 and 399, inclusive; “COL” is a placeholder for a non-zero-padded integer between 0 and 599, inclusive; the first row number is no greater than the second row number; the first column number is no greater than the second column number

Examples

0

{"0 292 399 307"}
{ 116800, 116800 }

The masking layer is depicted below in a 1: 4 scale diagram.

1

{"48 192 351 207", "48 392 351 407", "120 52 135 547", "260 52 275 547"}
{ 22816, 192608 }

2

{"0 192 399 207", "0 392 399 407", "120 0 135 599", "260 0 275 599"}
{ 22080, 22816, 22816, 23040, 23040, 23808, 23808, 23808, 23808 }

3

{"50 300 199 300", "201 300 350 300", "200 50 200 299", "200 301 200 550"}
{ 1, 239199 }

Explanation

Simply use breadth-first search in order to complete this problem. If you are new to TopCoder, you may need some time to adapt yourself to the new coding style. It uses classes instead of standard input and standard outputs.

Source Code


#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class grafixMask
{
public:
    static const int maxn = 610, maxm = 410;
    bool occupied[maxn][maxm];
    bool flagged[maxn][maxm];
    int n, m;
    int bfs(int x_, int y_) {
        queue< pair<int, int> > que;
        que.push(make_pair(x_, y_));
        int res = 0;
        while (!que.empty()) {
            pair<int, int> pr = que.front();
            que.pop();
            int x = pr.first, y = pr.second;
            if (x < 1 || x > n || y < 1 || y > m)
                continue; // Out of bound
            if (occupied[x][y] || flagged[x][y])
                continue; // Already flagged as used
            res++;
            flagged[x][y] = true;
            que.push(make_pair(x - 1, y));
            que.push(make_pair(x, y + 1));
            que.push(make_pair(x + 1, y));
            que.push(make_pair(x, y - 1));
        }
        return res;
    }
    vector<int> sortedAreas(vector<string> rectangles)
    {
        n = 600, m = 400;
        vector<int> res;
        // Reading input in an awkward style...
        stringstream stm;
        for (vector<string>::iterator i = rectangles.begin(); i != rectangles.end(); i++) {
            stm.clear();
            stm << *i;
            int a, b, c, d;
            stm >> a >> b >> c >> d;
            for (int j = b; j <= d; j++)
                for (int k = a; k <= c; k++)
                    occupied[j + 1][k + 1] = true; // Ranged in (x, y)
        }
        // Retrieving output...
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (!occupied[i][j] && !flagged[i][j])
                    res.push_back(bfs(i, j));
        sort(res.begin(), res.end());
        return res;
    }
};