I have been stuck at the problem grafixMask for a day now. This is the code I wrote following the pseudocode in the tutorial for DFS. I think that my code is not respecting the condition which decides which grid to include resulting in wrong answer but I can't figure out how to fix it.
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
const int ROWS = 400;
const int COLUMNS = 600;
class grafixMask {
public:
bool visited[ROWS][COLUMNS];
vector<int> result;
vector<int> sortedAreas (vector<string> rectangles) {
// initialize graph
for (int row = 0; row < ROWS; row++)
for (int column = 0; column < COLUMNS; column++)
visited[row][column] = false;
for (string rec: rectangles) {
int r1, c1, r2, c2;
istringstream ss(rec);
ss >> r1 >> c1 >> r2 >> c2;
// set rectangular masks
for(int i = r1; i <= r2; i++)
for (int j = c1; j <= c2; j++)
visited[i][j] = true;
for (int row = 0; row < ROWS; row++)
for (int column = 0; column < COLUMNS; column++)
if (!visited[row][column])
result.push_back(doFill(row, column)); // find all connected points enclosed by masks
}
sort(result.begin(), result.end());
return result;
}
int doFill(int row, int column){
int res = 0;
stack<pair<int, int> > s;
s.push(make_pair(row, column));
while(!s.empty()) {
pair<int, int> p = s.top();
int r = p.first;
int c = p.second;
s.pop();
if (r < 0 || r >= 400 || c < 0 || c >= 600 || visited[r][c]) continue;
visited[r][c] = true;
res++; // we covered additional area
s.push(make_pair(r-1, c));
s.push(make_pair(r+1, c));
s.push(make_pair(r, c-1));
s.push(make_pair(r, c+1));
}
return res;
}
};
Aucun commentaire:
Enregistrer un commentaire