grafixMask.cpp

// Solution for grafixMask  from TC SRM211
#include <bits/stdc++.h>
using namespace std;

// using DFS approach
class grafixMask
{
    public:
        vector<int> sortedAreas(vector <string> rectangles)
        {
            bool bitmap[400][600];
            memset(&bitmap[0], 0, sizeof(bitmap));
            for (auto s : rectangles) {
                int coord[4];
                int i = 0;
                size_t pos = 0;
                while (i < 4) {
                    size_t posNew = s.find(' ', pos);
                    std::cout << s.substr(pos, posNew - pos) << "\n";
                    coord[i] = atoi( s.substr(pos, posNew - pos).c_str() );
                    ++i; pos = posNew + 1;
                }

                for (int i = 0; i < 400; ++i) {
                    for (int j = 0; j < 600; ++j) {
                        if ((i >= coord[0] && i <= coord[2]) && (j >= coord[1] && j <= coord[3]))
                            bitmap[i][j] = true;

                    }
                }
            }

            vector<int> res;
            for (int i = 0; i < 400; ++i) {
                for (int j = 0; j < 600; ++j) {
                    if (!bitmap[i][j]) {
                        queue< pair<int, int> > q; q.push( make_pair(i, j) );
                        int n = 0;
                        while (!q.empty()) {
                            auto cur = q.front(); q.pop();
                            if ( cur.first < 0 || cur.first >= 400 || cur.second < 0 || cur.second >=600 || bitmap[cur.first][cur.second])
                                continue;
                            bitmap[cur.first][cur.second] = true;
                            q.push( make_pair(cur.first - 1, cur.second) );
                            q.push( make_pair(cur.first + 1, cur.second) );
                            q.push( make_pair(cur.first, cur.second - 1) );
                            q.push( make_pair(cur.first, cur.second + 1) );
                            ++n;
                        }
                        res.push_back(n);
                    }
                }
            }

            sort(res.begin(), res.end());
            return res;
        }
};

// using DisjointSet datastructure