asp网站背景,it外包公司前景如何,简述网站内容如何优化,公司装修通知告示怎么写本次n皇后问题主要通过dfs#xff08;深度优先搜索#xff09;实现#xff0c;加深对深度优先搜索的理解。 文章目录 前言 一、n皇后问题 二、算法思路 三、使用步骤 1.代码如下 2.读入数 3.代码运行结果 总结 前言 本次n皇后问题主要通过dfs#xff08;深度优先搜索#… 本次n皇后问题主要通过dfs深度优先搜索实现加深对深度优先搜索的理解。 文章目录 前言 一、n皇后问题 二、算法思路 三、使用步骤 1.代码如下 2.读入数 3.代码运行结果 总结 前言 本次n皇后问题主要通过dfs深度优先搜索实现加深对深度优先搜索的理解。 提示以下是本篇文章正文内容下面案例可供参考
一、n皇后问题
n皇后问题是指将n个皇后放到n*n的棋盘上面皇后放置具有一定的规则即每个皇后不能放在同一行同一列同一斜线上。
现在给定整数 n请你输出所有的满足条件的棋子摆法。
每个解决方案占 n行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
数据范围
1≤n≤9
二、算法思路
我们引入二维字符数组g来存储棋盘和皇后皇后用字符‘Q’表示棋盘该空格上什么也没有用字符‘.’表示。分别引入一维布尔类型数组col、dg、udg分别表示列、斜对角线、、反斜对角线。 图1.1 思路模拟
关于对角线我们可以通过截距来表示即如果这些点都在同一个对角线线上那么他们把横纵坐标代入算出来的截距b一定是相同的。反斜对角线的b yx那么斜对角线b y - x又因为这个值可以为负的我们加一个n来保证值不会变成负的那么范围会变成(0,2n)所以我们的布尔类型数组要开2倍的n大小。(注因为我们每行就放一个皇后那么行就不需要开布尔类型数组判断)。
我们通过dfs来传入参数x表示每一行当然递归的出口就是我们把每一行都处理完当此时的x n时(x从0到开始)我们把此时的棋盘打印即可。然后dfs内部再枚举每一列y当col[y] dg[y-xn] udg[yx] false那么就说明此时可以放置皇后然后将g[x][y] Q再将ol[y] dg[y-xn] udg[yx] true然后递归的处理下一行即dfsx1当第一轮递归结束后此时我们就把棋子进行回溯操作把所有的东西恢复到初始状态即棋盘全部变为‘.’和修改过的布尔类型数组变为false第一次处理是将第一行第一列放第一个皇后然后递归处理后续情况第二次处理是将第一行第二列放第一个皇后递归处理最后的情况最后知道第一行最后一列放第一个皇后此时我们就将所有的情况都考虑到了。
当引入4个皇后到4*4棋盘的情况 图1.2模拟一
图1.2展示当 我们让第一行第一列放置第一个皇后所出现的情形无法得到放置4个皇后的情况。 图1.3模拟二 图1.4模拟三
图1.3和图1.4模拟的是当皇后分别放在 第一行第二列和第一行第三列且成功在棋盘上放置4个皇后的情况。 图1.5模拟四
图1.5模拟的是当皇后放在第一行第四列的所有情况无法在棋盘上放置4个皇后。
三、使用步骤
1.代码如下
import java.io.*;
import java.util.*;public class n皇后问题 {static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static int n 0;//存储路径static char[][] g;//列static boolean[] col;//斜对角线static boolean[] dg;//斜写对角线static boolean[] udg;public static void main(String[] args) {Scanner sc new Scanner(br);n sc.nextInt();g new char[20][20];col new boolean[20];dg new boolean[20];udg new boolean[20];for(int i 0;i n;i){for(int j 0;j n;j){g[i][j] .;}}dfs(0);pw.flush();}public static void dfs(int u){//当un时说明我们找到一种方案if(u n){for(int i 0;i n;i){for(int j 0;j n;j){pw.print(g[i][j]);}pw.println();}pw.println();return;}//行数int x u;//枚举每一列for(int y 0;y n;y){// 列 对角线 反对角线if(col[y] false dg[y-xn] false udg[yx] false){g[x][y] Q;//表示这些位置不能放了col[y] dg[y-xn] udg[yx] true ;dfs(x1);//回溯g[x][y] .;col[y] dg[y-xn] udg[yx] false;}}}
}2.读入数
4
3.代码运行结果
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q.. 总结
我们主要理解dfs的原理懂得如何套用dfs代码模板最重要的不要忘记进行回溯操作。
