题解 | #牛吃草问题#
牛吃草问题
https://www.nowcoder.com/practice/c6e33216019a4ea9bf4015e9868dd225
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ private int ans = 0; public int totalNCow(int n) { int[] pos = new int[n]; help(pos, n, 0); return ans; } private boolean isValid(int[] pos, int row, int col) { for (int i = 0; i < row; i++) { if (row == i || col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i])) { return false; } } return true; } private void help(int[] pos, int n, int row) { if (row == n) { ans++; return; } for (int i = 0; i < n; i++) { if (isValid(pos, row, i)) { pos[row] = i; help(pos, n, row + 1); } } } }
知识点:
递归回溯。
解答分析:
经典八皇后问题,从上到下一行一行填入,枚举填在哪一列,使用递归的方式,一层一层去遍历获取结果。回溯后记得恢复现场。
编程语言:
java语言。