题解 | #牛吃草问题#

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    // 检测对角线是否有放置牛
    bool check(vector<vector<int>>& grid, int start, int i) {
        bool flag = true;
        int cur_i = start-1, cur_j = i-1;
        while (cur_i >= 0 && cur_j >= 0) {
            if (grid[cur_i][cur_j]) {
                flag = false;
                break;
            }
            cur_i--, cur_j--;
        }
        if (!flag) return false;
        cur_i = start-1, cur_j = i+1;
        while (cur_i >= 0 && cur_j < grid[0].size()) {
            if (grid[cur_i][cur_j]) {
                flag = false;
                break;
            }
            cur_i--, cur_j++;
        }
        if (!flag) return false;
        return true;
    }
    
    // vis用来表示列中选过的位置，start表示当前要选的行
    void backtrace(vector<vector<int>>& grid, vector<int>& vis, int start, int& ans) {
        // 如果要选的超过了，则表示满足一种方法
        if (start >= grid.size()) {
            ans++;
            return;
        }
        // 这么每次都是从头开始的，所以需要有vis数组进行记录
        for (int i = 0; i < vis.size(); i++) {
            if (!vis[i] && check(grid, start, i)) {
                // 当位置合适之后，vis和grid都需要修改
                vis[i] = 1;
                grid[start][i] = 1;
                backtrace(grid, vis, start+1, ans);
                grid[start][i] = 0;
                vis[i] = 0;
            }
        }
    }

    int totalNCow(int n) {
        // write code here
        int ans = 0;
        for (int i = 0; i < n; i++) {
            vector<int> vis(n, 0);
            vis[i] = 1;
            vector<vector<int>> grid(n, vector<int>(n));
            grid[0][i] = 1;
            backtrace(grid, vis, 1, ans);
        }   
        return ans;
    }
};