net服装网站建设,深圳建英文网站,适合个人做外贸的网站,如何去掉wordpress底部版权n-皇后问题1.题目2.基本思想3.代码实现1.题目
n−皇后问题是指将 n 个皇后放在 nn 的国际象棋棋盘上#xff0c;使得皇后不能相互攻击到#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n#xff0c;请你输出所有的满足条件的棋子摆法。
…
n-皇后问题1.题目2.基本思想3.代码实现1.题目
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n请你输出所有的满足条件的棋子摆法。
输入格式 共一行包含整数 n。
输出格式 每个解决方案占 n 行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
注意行末不能有多余空格。
输出方案的顺序任意只要不重复且没有遗漏即可。
数据范围 1≤n≤91≤n≤91≤n≤9
输入样例 4 输出样例 .Q… …Q Q… …Q. …Q. Q… …Q .Q… 2.基本思想 DFS 时间复杂度O(n!) 正对角线y-xc,cxy,c这里代表截距反对角线yxccy-x,所以这里的c可能是负的但作为数组下标不能是负的所以我们把反对角线加上一个偏移量cy-xn是没影响的因为截距最大是n也可以加比n大的任何数 用截距表示对角线截距相同就说明是同一条对角线
核心目的找一些合法的下标来表示dg或udg是否被标记过所以如果你愿意你取 udg[nn−ui]
也可以只要所有(u,i)对可以映射过去就行.
3.代码实现
import java.util.Scanner;public class _843n皇后问题 {static Scanner sc new Scanner(System.in);static int N 20;//增加 了一个 偏移量 n 需要 开 20static int n;static char path[][] new char[N][N];//保存 路径信息static boolean[] col new boolean[N];// bool数组用来判断搜索的下一个位置是否可行 col列dg对角线udg反对角线static boolean[] dg new boolean[N];static boolean[] udg new boolean[N];public static void main(String[] args) {n sc.nextInt();for (int i 0; i n; i)for (int j 0; j n; j)path[i][j] .;dfs(0);}private static void dfs(int u) {if (u n) {//表示 已经搜素了n行 输出这条路径 信息for (int i 0; i n; i) {for (int j 0; j n; j)System.out.print(path[i][j]);System.out.println();//换行}System.out.println();return;}//对n个位置按行搜索for (int i 0; i n; i) {if (!col[i] !dg[i u] !udg[n i - u]) {path[u][i] Q;col[i] dg[u i] udg[n i - u] true;dfs(u 1);//枚举 下一行//恢复 回溯col[i] dg[u i] udg[n i - u] false;path[u][i] .;}}}
}
