网站建设pdf微盘,做网站必须要注册公司么,做网站心得,国外做mg动画的网站大全题目描述 检查一个如下的6 x 6的跳棋棋盘#xff0c;有六个棋子被放置在棋盘上#xff0c;使得每行、每列有且只有一个#xff0c;每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述#xff0c;第i个数字表示在第i行…题目描述 检查一个如下的6 x 6的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述第i个数字表示在第i行的相应位置有一个棋子如下
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
//以下的话来自usaco官方不代表洛谷观点
特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式这是作弊。如果你坚持作弊那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了
输入输出格式 输入格式 一个数字N (6 N 13) 表示棋盘是N x N大小的。
输出格式 前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。
输入输出样例 输入样例#1 6 输出样例#1 2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4 说明 题目翻译来自NOCOW。
USACO Training Section 1.5
解析单纯的八皇后问题注意输出就可以了但是不巧的是下面的代码最后一个测试点总是超时。
import java.util.Scanner;public class Main2 {static int n;static int cnt 0;static int[][] chess;public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();chess new int[n1][n1];f(0);System.out.println(cnt);}private static void f(int row) {// TODO Auto-generated method stubif (row n - 1) {cnt;if(cnt 3) {print();}}for (int i 0; i n; i) {for (int j 0; j n; j) {chess[row][j] 0;}chess[row][i] 1;if (isSafety(row, i)) {f(row 1);}}}private static void print() {// TODO Auto-generated method stubfor (int i 0; i n; i) {for (int j 0; j n; j) {if (chess[i][j] ! 0) {System.out.print((j1) );}}}System.out.println();}private static boolean isSafety(int row, int col) {// TODO Auto-generated method stubint step 1;while (row - step 0) {if (chess[row-step][col] 1) {return false;}if (col - step 0 chess[row-step][col-step] 1) {return false;}if (col step n chess[row-step][colstep] 1) {return false;}step;}return true;}
}
看了题解发现一个非常妙解法而且别上面的解法要略快一点。
import java.util.Scanner;public class Main {static int n;static int cnt 0;static boolean[][] check;static int[] ans;public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();check new boolean[3][28];ans new int[14];eq(1);System.out.println(cnt);}private static void eq(int line) {// TODO Auto-generated method stubif (line n) {cnt;if (cnt 3) {return;} else {for (int i 1; i n; i) {System.out.print(ans[i] );}System.out.println();}}/*** ans[] 存储每一行的信息* check[0][] 存储每一列的信息* check[1][line i] 存储从左上到右下的信息* check[2][line - i n] 存储从右上到左下的信息* */ for (int i 1; i n; i) {if ((!check[0][i]) (!check[1][line i]) (!check[2][line - i n])) {ans[line] i;check[0][i] true;check[1][line i] true;check[2][line - i n] true;eq(line 1);check[0][i] false;check[1][line i] false;check[2][line - i n] false;}}}
}
