题解 | #牛吃草问题#
牛吃草问题
https://www.nowcoder.com/practice/c6e33216019a4ea9bf4015e9868dd225
考察的知识点:回溯;
解答方法分析:
- 创建一个大小为 n 的数组 row,用于存储每行牛所在的列索引。
- 创建一个大小为 n 的数组 col,用于标记每列是否已经有牛。
- 创建一个大小为 2n-1 的数组 diagonal1,用于标记每个主对角线是否已经有牛。
- 创建一个大小为 2n-1 的数组 diagonal2,用于标记每个副对角线是否已经有牛。
- 定义一个变量 count,用于统计合法的放牧方案数量。
- 定义一个递归函数 backtrack,用于尝试放置牛的位置。如果 row 的索引已经达到 n,说明已经成功放置了 n 头牛,将 count 加一。遍历当前行的每个列,如果该列未被占用,并且主对角线和副对角线上都没有牛,则可以尝试将该牛放在该位置。将该列标记为已占用。将主对角线和副对角线上对应的位置标记为已占用。将该行的索引记录在 row 数组中。递归尝试放置下一行的牛。回溯,将当前位置的状态恢复。
- 调用递归函数 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; } } } };