题解 | #牛吃草问题#

考察知识点：回溯

题目分析：

本题是典型的n皇后问题。需要在草场上的每一行放置一头牛，递归的入口就是索引是0的哪一行。

递归时，看该行的每一列是否可以放置牛，如果可以放置牛，那么就尝试在这个地方放置牛，并记录这一列已被占用，两个相关的斜线上的位置也被占用。当然在这里放置最终可能有解， 也有可能无解。在有解时，即row == n时，可以将结果更新。无解时，row的值无法到达n，所以就会回溯回去。注意回溯后应该还原现场。

对于对角线，可以分别记录一个从左下到右上的斜线，和一个从左上到右下的斜线。可以通过截距的值明确是该斜率下的哪一条线。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int col[10] = {0}, dg[20] = {0}, ndg[20] = {0};

    void dfs(int row, int n, int &res) {
        if (row == n) {
            res++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dg[row + i] && !ndg[n + row - i]) {
                col[i] = dg[row + i] = ndg[n + row - i] = 1;
                dfs(row + 1, n, res);
                col[i] = dg[row + i] = ndg[n + row - i] = 0;
            }
        }
    }
    
    int totalNCow(int n) {
        // write code here
        int res = 0;
        dfs(0, n, res);
        return res;
    }
};