USACO Section 1.5.4 [Checker Challenge] Java例题

USACO Section 1.5.4 [Checker Challenge] Java题解
题意分析：
该题是需要深度优化的八皇后问题，首先看一下，经典八皇后问题的一般解法：

public class Queens {private final static int MAX = 8;// site[i] = j => col:i row:jprivate static int[] site = new int[MAX];private static boolean check(int col){for(int i = 0; i < col; i++){if(site[i] == site[col] || //不在一行上Math.abs(site[col]-site[i]) == col - i) //也不在对角线上return false;}return true;}private static void queens(int col){if(col == MAX);//output();elsefor(int i = 0; i < MAX; i ++){site[col] = i;if(check(col))queens(col+1);}}public static void main(String[] args){queens(0);}}

该题不一样的地方有：
1）N不是8，而是6-13
2）需输出结果个数和头3个结果

解题思路：
1）只考虑一半的column结果乘以2，另一半认为是沿中心垂直对称的。如果N是奇数，则结果中数量要补上中间那条column。
2）优化对角线的判断，使之成为搜索的状态，而不是每次判断都要重新算（这里和The Clocks这一题有异曲同工）。可以发现两条对角线上的元素特征分别是i+j以及i-j+N是相同的，因此开两个2×N大小的int数组来记录占用情况。注意此处不是boolean而是int的原因是占用的影响有累积效应。
3）同理，可以优化列占用情况。（和上述八皇后不同的是，这题必须一行一行考虑）
4）小数据的情况要特别考虑，该题中N为6时，优化check是可以用的，但是由于要输出3个结果，只查找一半是不可行的，要查找全部。

代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/checker.java

查看更多 下一篇