分享一道算法题

一个3行3列的矩阵(九宫格)

给定6个int,h1,h2,h3,w1,w2,w3,分别代表行总和与列总和，总和范围在[3-30]

试问在9宫格中填写正整数，有多少种填写方式？

class Solution {
 public:
  void filter() {
    // tmp 1, 2, 3, 4
    res[0][0] = tmp[0];
    res[0][1] = tmp[1];
    res[1][0] = tmp[2];
    res[1][1] = tmp[3];
    res[0][2] = h1 - res[0][0] - res[0][1];
    res[1][2] = h2 - res[1][0] - res[1][1];
    res[2][0] = w1 - res[0][0] - res[1][0];
    res[2][1] = w2 - res[0][1] - res[1][1];
    res[2][2] = h3 - res[2][0] - res[2][1];
  }
  void dfs(int pos) {
    if (pos == 4) {
      filter();
      if (valid()) {
        ++count_;
      }
    } else {
      for (int i = 1; i <= 28; i++) {
        tmp[pos] = i;
        dfs(pos + 1);
      }
    }
  }

  bool valid() {
    for (int i = 0; i < 3; i++) {
      for (size_t j = 0; j < 3; j++) {
        if (res[i][j] <= 0) return false;
      }
    }

    return res[0][0] + res[0][1] + res[0][2] == h1 &&
           res[1][0] + res[1][1] + res[1][2] == h2 &&
           res[2][0] + res[2][1] + res[2][2] == h3 &&
           res[0][0] + res[1][0] + res[2][0] == w1 &&
           res[0][1] + res[1][1] + res[2][1] == w2 &&
           res[0][2] + res[1][2] + res[2][2] == w3;
  }
  int func(const vector<int>& data) {
    res.resize(3, vector<int>(3, 0));
    tmp.resize(4, 0);
    h1 = data[0], h2 = data[1], h3 = data[2];
    w1 = data[3], w2 = data[4], w3 = data[5];
    dfs(0);
    return count_;
  }

 private:
  int count_ = 0;
  int h1, h2, h3, w1, w2, w3;
  vector<int> tmp;
  vector<vector<int>> res;
};