题解 | #牛吃草问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public static int amount = 0;
    public static int totalNCow (int n) {
        // write code here
        boolean[] visited = new boolean[n + 1];
        search(n, visited, 1, new LinkedList<>());
        return amount;
    }

    public static void search(int n, boolean[] visited, int rows,
                              LinkedList<Integer> linkedList) {
        for (int i = 0; i < linkedList.size(); i++) {
            for (int j = 0; j < linkedList.size(); j++) {
                if (i != j &&
                        Math.abs(linkedList.get(i) - linkedList.get(j)) == Math.abs(j - i)) {
                    return;
                }
            }
        }
        if (rows > n) {
            amount++;
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (!visited[j]) {
                linkedList.add(j);
                visited[j] = true;
                search(n, visited, rows + 1, linkedList);
                linkedList.remove(linkedList.size() - 1);
                visited[j] = false;
            }
        }
    }
}

本题主要考察的知识点是递归，所用编程语言是java。

本题跟N皇后题目有些类似，都是相同的解法，首先我们根据题目意思任意两头牛不能属于同一行，同一列，对角线。不能属于同一行同一列好办，我们可以定义一个大小为n的一维数组，数组的下标代表处于相应的某一行，数组相应下标下存储的值代表某一列的位置，然后我们需要比较数组观察数组里面的值是否都不在对角线上。我们根据数组当中任意两个值相减的绝对值不等于相应下标相减的绝对值判断不处于同一对角线上。