mercredi 10 juillet 2019

Topcoder - grafixMask, Implementing DFS

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