题解 | #牛吃草问题#

知识点

回溯

解题思路

可以从第一行开始放置牛，逐行进行探索。在每一行中，对于当前位置，我们检查是否可以放置一头牛。如果可以放置，我们就继续搜索下一行；如果不能放置，我们尝试下一个位置。直到在最后一行放置了一头牛。通过调用totalNow方法并传入牛的数量n，即可获取不同方案的数量。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int totalNCow(int n) {
        if (n <= 0) {
            return 0;
        }

        int[] count = new int[1]; // 用于记录方案数量的计数器

        backtrack(0, new int[n], count);

        return count[0];
    }

    private void backtrack(int row, int[] placement, int[] count) {
        int n = placement.length;

        // 如果已经在最后一行放置了一头牛，说明找到了一个有效的方案
        if (row == n) {
            count[0]++;
            return;
        }

        // 在当前行的每一个位置尝试放置一头牛
        for (int col = 0; col < n; col++) {
            if (canPlace(row, col, placement)) {
                placement[row] = col; // 在当前位置放置一头牛

                // 继续搜索下一行
                backtrack(row + 1, placement, count);

                placement[row] = 0; // 恢复当前位置为空
            }
        }
    }

    private boolean canPlace(int row, int col, int[] placement) {
        // 检查当前位置的列和对角线是否没有其他牛
        for (int i = 0; i < row; i++) {
            if (placement[i] == col || Math.abs(row - i) == Math.abs(col - placement[i])) {
                return false;
            }
        }

        return true;
    }
}