algorithm - Topcoder - grafixMask，实现 DFS

Question

我一直卡在问题grafixMask现在一天。这是我按照 DFS 教程中的伪代码编写的代码。我认为我的代码不遵守决定包含哪个网格的条件，导致错误的答案，但我不知道如何解决它。

    #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;
        }
    };

Answer 1

无数次地检查代码，我终于发现了我做错了什么: 查看我将输入作为 rectangles 的代码。在这里我不小心包含了 for 循环来查找网格的所有连接组件。所以正确的代码是:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

const int ROWS = 400;
const int COLUMNS = 600;
bool visited[400][600] = {false};

class grafixMask {
 public:
  vector<int> result;

  vector<int> sortedAreas(vector<string> rectangles) {
    for (auto rec : rectangles) {
      istringstream ss(rec);
      int r1, c1, r2, c2;
      ss >> r1 >> c1 >> r2 >> c2;
      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));
        }

    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() == false) {
      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

      int dirRow[] = {1, -1, 0, 0};
      int dirCol[] = {0, 0, 1, -1};

      for (int i = 0; i < 4; i++) {
        int newRow = r + dirRow[i];
        int newCol = c + dirCol[i];
        if (newRow >= 0 && newRow < 400 && newCol >= 0 && newCol < 600 &&
            !visited[newRow][newCol]) {
          s.push(make_pair(newRow, newCol));
        }
      }
    }
    return res;
  }
};