题解 | #牛吃草问题#

• 题目考察的知识点 : 递归回溯，n皇后变种
• 题目解答方法的文字分析：

1. 拿n皇后的题解改一下
2. 遍历整个棋盘，尝试在每一行放置一个皇后。具体地，我们定义一个数组queens，用于存储每行中已经放置的皇后所在的列号；定义三个集合cols、diagonals1和diagonals2，分别存储已经被占据的列、正对角线和反对角线。然后，我们定义一个backtrack函数，在函数中遍历每一列，判断是否可以在该列放置皇后。如果可以放置，则将该位置标记为已占据，并尝试向下一行继续放置皇后。如果无法放置，则回溯到上一行

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
    def totalNCow(self, n: int) -> int:
        # 定义一个数组，用于存储每行中已经放置的皇后所在的列号
        queens = [-1] * n
        # 定义三个集合，分别存储已经被占据的列、正对角线和反对角线
        cols, diagonals1, diagonals2 = set(), set(), set()
        # 定义一个变量，用于记录方案数
        self.count = 0

        # 定义一个函数，用于尝试在第row行放置皇后
        def backtrack(row):
            # 如果已经放置了n个皇后，则找到了一种合法方案
            if row == n:
                self.count += 1
            else:
                for col in range(n):
                    diagonal1 = row - col  # 计算正对角线的编号
                    diagonal2 = row + col  # 计算反对角线的编号
                    # 如果当前列、正对角线和反对角线上都没有被占据，则可以放置皇后
                    if (
                        col not in cols
                        and diagonal1 not in diagonals1
                        and diagonal2 not in diagonals2
                    ):
                        queens[row] = col  # 标记第row行的皇后位置为col列
                        cols.add(col)  # 将第col列标记为已被占据
                        diagonals1.add(diagonal1)  # 将正对角线编号标记为已被占据
                        diagonals2.add(diagonal2)  # 将反对角线编号标记为已被占据
                        backtrack(row + 1)  # 继续搜索下一行
                        queens[row] = -1  # 回溯，将第row行的皇后位置重置为未占据状态
                        cols.remove(col)  # 将第col列重新标记为未被占据
                        diagonals1.remove(diagonal1)  # 将正对角线编号重新标记为未被占据
                        diagonals2.remove(diagonal2)  # 将反对角线编号重新标记为未被占据

        backtrack(0)  # 从第0行开始放置皇后
        return self.count