DFS

DFS：经可能深的搜索

题目

AcWing

842 排列数字
843 n皇后问题

Ac842 排列数字

描述

给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

解答

package Chapter3;

/**
 * 
 * ACWing 842  全排列
 * dfs  深度优先搜索
 * 
 * 
 * @author vccyb
 *
 */

import java.io.*;
import java.util.*;

public class P842 {
	private static final int N = 10;
	//path[] 存储状态
	private static int[] path = new int[N];
	//st表示那个数用过了
	private static boolean[] st = new boolean[N];
	
	public 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++){
			if(!st[i]){  //当那个数没有被用到时
				path[u] = i;
				st[i] = true;
				dfs(u+1,n);
				//dfs函数结束的时候
				//path[u]=0 会被覆盖
				st[i]=false;//回溯，很关键，你递归完了修改状态
			}
		}	
		
	}
	
	public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        dfs(0,n);
	}
	

}

Ac843 n皇后问题

描述

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

解答

解法1

package Chapter3;

/**
 * 
 * AcWing 843 n-皇后问题
 * dfs 给我搜	
 * 
 * @author vccyb
 *
 */
import java.io.*;
import java.util.*;

public class P843 {
    static int N = 10,n;
    static boolean row[] = new boolean[N];
    static boolean col[] = new boolean[N];
    static boolean dg[] = new boolean[N*2];//对角线的个数是行数的两倍-1
    static boolean udg[] = new boolean[N*2];//对角线的个数是行数的两倍-1
    static char path[][] = new char[N][N];
    
    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);
	}
    
    private 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;
    	}
    	
    	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]='.';
    			
    		}
    	}
    }

}

解答二

package Chapter3;

import java.util.Scanner;

/**
 * AcWing P843
 * n皇后问题解法二
 * @author vccyb
 *
 */
public class P483_2 {
	static int N = 10,n;
    static boolean row[] = new boolean[N];
    static boolean col[] = new boolean[N];
    static boolean dg[] = new boolean[N*2];//对角线的个数是行数的两倍-1
    static boolean udg[] = new boolean[N*2];//对角线的个数是行数的两倍-1
    static char path[][] = new char[N][N];
    
    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,0,0);

		
	}
    
    static void dfs(int x, int y, int s){
    	//x行，y列，s皇后数量
    	if(y==n){
    		y=0;
    		x++;
    	}
    	
    	if(x==n){
    		if(s==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;
    	}
    	
    	//当前格子的两种选择
    	//不放皇后
    	dfs(x,y+1,s);
    	//放皇后
    	if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]) {
    		path[x][y]='Q';
    		row[x]=true;col[y]=true;dg[x+y]=true;udg[x-y+n]=true;
    		dfs(x,y+1,s+1);
    		row[x]=false;col[y]=false;dg[x+y]=false;udg[x-y+n]=false;
            path[x][y]='.';
    	}
    }

}