SRM 211 DIV-1 500 grafixMask

Problem Statement

This is a typical problem that is easily solvable using Flood Fill / BFS / DFS. The first challenge is to digest the problem quickly, and implement the code to parse input and extract interested information (in this case, the graph representation.). The second challenge is to to make sure only visit a node once.

vector<int> parseString(string input) {
  istringstream iss(input);
  vector<string> tokens{istream_iterator<string>{iss},
    istream_iterator<string>{}};
  vector<int> ret;
  for (auto &str : tokens) {
    ret.emplace_back(stoi(str));
  }
  return ret;
};

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles) {
      const int ROWS = 400, COLS = 600;
      vector<vector<bool>> bitmap(ROWS, vector<bool>(COLS, false));
      vector<int> ret;
      for (auto &rec : rectangles) {
        auto vec = parseString(rec);
        for (int i = vec[0]; i <= vec[2]; ++i) {
          for (int j = vec[1]; j <= vec[3]; ++j) {
            bitmap[i][j] = true;
          }
        }
      }

      for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
          if (bitmap[i][j]) continue;
          int area = 0;
          stack<pair<int,int>> stack;
          stack.push(make_pair(i, j));

          while (!stack.empty()) {
            auto pos = stack.top();
            stack.pop();
            int x = pos.first, y = pos.second;
            if (bitmap[x][y]) continue;
            bitmap[x][y] = true;
            ++area;

            int dirx[] = {1, -1, 0, 0};
            int diry[] = {0, 0, 1, -1};
            for (int k = 0; k < 4; ++k) {
              int xx = x + dirx[k], yy = y + diry[k];
              if (xx >= 0 && xx < 400 && yy >= 0 && yy < 600 && !bitmap[xx][yy]) {
                stack.push(make_pair(xx, yy));
              }
            }
          }
          ret.push_back(area);
        }
      }
      sort(ret.begin(), ret.end());
      return ret;
    }
}