DFS

what DFS?
DFS： 深度优先搜索

用个全排列的问题来看

题解

package Chapter3;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class P842 {static final int N = 10;static int[] path = new int[N];static boolean[] st = new boolean[N];static void dfs(int u, int n){if(u==n){for(int i=0;i<n;i++){System.out.print(path[i]+" ");}System.out.println();return;}//n=3 1 2 3从1开始for(int i=1;i<=n;i++){//默认是false  //1. 用过了 true 2.没用过 falseif(!st[i]){//没用过的化path[u] = i; // 存st[i] = true; //记为用过dfs(u+1,n);// 继续遍历st[i] = false; //遍历回来了，回溯，恢复现场}}	}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());dfs(0,n);}}

题目
经典的n皇后问题

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上

题解2

package Chapter3;import java.util.Scanner;/*** n皇后问题* @author vccyb**/
public class P843 {static final int N = 10;static int n;static boolean row[] = new boolean[N];static boolean col[] = new boolean[N];static boolean dg[] = new boolean[N*2];static boolean udg[] = new boolean[N*2];static char[][] path = new char[N][N];static void dfs(int u){if(u==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;}//一行一行来  u行i列for(int i=0;i<n;i++){if(!col[i]&&!dg[i+u]&&!udg[i-u+n]){path[u][i]='Q';col[i]=true;dg[i+u]=true;udg[i-u+n]=true;//标识使用dfs(u+1);col[i]=false;dg[i+u]=false;udg[i-u+n]=false;path[u][i]='.'; //回溯}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for(int i=0;i<n;i++){for(int j=0;j<n;j++){path[i][j]= '.';}}dfs(0);}}

总结

dfs

• 顺序是很重要的，一定要搞懂顺序
• 回溯很重要，当到底了一定要恢复现场，回溯