题解 | #牛吃草问题#

考察的知识点：回溯；

解答方法分析：

1. 创建一个大小为 n 的数组 row，用于存储每行牛所在的列索引。
2. 创建一个大小为 n 的数组 col，用于标记每列是否已经有牛。
3. 创建一个大小为 2n-1 的数组 diagonal1，用于标记每个主对角线是否已经有牛。
4. 创建一个大小为 2n-1 的数组 diagonal2，用于标记每个副对角线是否已经有牛。
5. 定义一个变量 count，用于统计合法的放牧方案数量。
6. 定义一个递归函数 backtrack，用于尝试放置牛的位置。如果 row 的索引已经达到 n，说明已经成功放置了 n 头牛，将 count 加一。遍历当前行的每个列，如果该列未被占用，并且主对角线和副对角线上都没有牛，则可以尝试将该牛放在该位置。将该列标记为已占用。将主对角线和副对角线上对应的位置标记为已占用。将该行的索引记录在 row 数组中。递归尝试放置下一行的牛。回溯，将当前位置的状态恢复。
7. 调用递归函数 backtrack()。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    int totalNCow(int n) {
        vector<int> row(n, -1);
        vector<bool> col(n, false);
        vector<bool> diagonal1(2 * n - 1, false);
        vector<bool> diagonal2(2 * n - 1, false);
        int count = 0;
        backtrack(row, col, diagonal1, diagonal2, count, 0, n);
        return count;
    }

  private:
    void backtrack(vector<int>& row, vector<bool>& col, vector<bool>& diagonal1,
                   vector<bool>& diagonal2, int& count, int r, int n) {
        if (r == n) {
            count++;
            return;
        }
        for (int c = 0; c < n; c++) {
            if (!col[c] && !diagonal1[r + c] && !diagonal2[r - c + n - 1]) {
                col[c] = true;
                diagonal1[r + c] = true;
                diagonal2[r - c + n - 1] = true;
                row[r] = c;
                backtrack(row, col, diagonal1, diagonal2, count, r + 1, n);
                col[c] = false;
                diagonal1[r + c] = false;
                diagonal2[r - c + n - 1] = false;
                row[r] = -1;
            }
        }
    }
};