题解 | #牛吃草问题#

八皇后问题：

解题思路：

1. 使用一个向量`cols`表示 `row`行放置了`col`列的牛; （也就是说[-1, 1,....,] 那个1表示在第二行的第一列放置了牛）
2. 遍历每一行 row
1. 在行内遍历每一个位置 col
2. 判断（row，col）位置上是否能够放牛
1. 查看cols的0~row-1的位置是否和(row，col)冲突
2. cols[i] = col 肯定不可以嘛，别人已经占了这个位置了
3. abs(cols[i] - col) = abs(i-row) 这个是嘛意思？
1. $\frac{abs(cols[i] - col)}{abs(i-row)} = 1$懂了吧，就是斜率为1，对角线上哪些位置的
3. 能放牛就放上去
1. 不能就返回false
4. 记得回溯回去

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    
    // 检查当前位置是否可以放牛
    bool isValid(vector<int>&cols,int row,int col){
        // 检查row行，col列位置是否可以放置牛
        for(int i=0;i<row;++i){
            // 如果i行已经在col位置放了牛
            // 或者i行放置的牛的位置在对角线上（斜率为1）
            if(cols[i] == col || abs(cols[i] - col) == abs(i-row)){
                return false;
            }
        }
        return true;
    }

    void backtrack(vector<int>&cols,int row,int &count){
        // cols的index表示行，值表示在第几列放了牛
        int n = cols.size();
        // 放置的牛的数量等于n，表示该位置合理
        if(row == n){
            count++;
            return;
        }
        // 遍历每一列，看是否能够放牛
        for(int col=0;col<n;col++){
            if(isValid(cols,row,col)){
                // 如果可以放牛就放上
                cols[row] = col;
                // 下一个位置是行数加1
                backtrack(cols,row+1,count);
                // 回溯回来
                cols[row] = -1;
            }
        }

    }

    int totalNCow(int n) {
        // 八皇后问题
        vector<int> cols(n,-1); // 记录每一行中放牛的列索引
        int count = 0;
        backtrack(cols,0,count);
        return count;
    }
};