DFS例题

深度优先遍历和广度优先遍历：可参考

深度优先遍历和广度优先遍历

数独游戏：

你一定听说过“数独”游戏。
如下图所示，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。

数独的答案都是唯一的，所以，多个解也称为无解。
本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。
本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。
格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。
输出9行，每行9个数字表示数独的解。
输入：

005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700

程序应该输出：

145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

再例如，输入：

800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400

程序应该输出：

812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

解题思路：

这里利用dfs来解题。

将每一种情况进行尝试。如果找到答案就退出。具体解法看代码

下面程序只求了一种解。

java代码示例：

import java.util.Scanner;

public class 数独 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[][] table = new char[9][9];
		for(int i = 0; i < 9; i++) {
			table[i]  = sc.nextLine().toCharArray();
		}
		dfs(table, 0, 0);
	}
	
	public static void dfs(char[][] table, int x, int y) {
		if(x == 9) { //如果x==9，则证明表格填完，找到答案。此时打印表格，并退出程序
			for(int i = 0; i < table.length; i++) {
				for(int j = 0; j < table.length; j++) {
					System.out.print(table[i][j] + " ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		if(table[x][y] == '0') {//虚位以待
			for(int i = 1; i <= 9; i++) {
				char ch = (char) ('0' + i);
				if(check(table, x, y, ch)) {//检查i是否合法
					table[x][y] = ch;
					//填下一个位置
					dfs(table, x + (y + 1) / 9, (y + 1) % 9);
				}
			}
			table[x][y] = '0';//回溯
		}else {
			dfs(table, x + (y + 1) / 9, (y + 1) % 9);
		}
	}

	private static boolean check(char[][] table, int x, int y, char ch) {
		//检查同行同列
		for(int l = 0; l < 9; l++) {
			if(table[x][l] == ch) return false;
			if(table[l][y] == ch) return false;
		}
		//检查小九宫格
		//  0 1 2  3 4 5  6 7 8
		for(int l = (x / 3) * 3; l < (x / 3 + 1) * 3; l++) {
			for(int m = (y / 3) * 3; m < (y / 3 + 1) * 3; m++) {
				if(table[l][m] == ch) return false;
			}
		}
		return true;
	}
}

程序运行结果：

005300000  //输入
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
1 4 5 3 2 7 6 9 8 //输出
8 3 9 6 5 4 1 2 7 
6 7 2 9 1 8 5 4 3 
4 9 6 1 8 5 3 7 2 
2 1 8 4 7 3 9 5 6 
7 5 3 2 9 6 4 8 1 
3 6 7 5 4 2 8 1 9 
9 8 4 7 6 1 2 3 5 
5 2 1 8 3 9 7 6 4 

070003600 //输入
009500004
060000000
090800300
080010050
002000090
000000030
500004100
006700080
2 7 5 4 8 3 6 1 9  //输出
3 1 9 5 6 2 8 7 4 
8 6 4 1 7 9 5 2 3 
6 9 7 8 2 5 3 4 1 
4 8 3 9 1 7 2 5 6 
1 5 2 3 4 6 7 9 8 
7 4 1 6 5 8 9 3 2 
5 3 8 2 9 4 1 6 7 
9 2 6 7 3 1 4 8 5

子集生成之二进制法：

请编写一个方法，返回某集合的所有非空子集。

给定一个int数组A和数组的大小int n，请返回A的所有非空子集。
保证A的元素个数小于等于20，且元素互异。

各子集内部从大到小排序,子集之间字典逆序排序

java解题示例：

import java.util.ArrayList;
import java.util.Arrays;

public class 子集生成及二进制法 {
	public static void main(String[] args) {
		char[] A = {'A', 'B', 'C'};
		ArrayList<ArrayList<Character>> subsets = getSubsets(A, A.length);
	    System.out.println(subsets);
	}
	
	public static  ArrayList<ArrayList<Character>> getSubsets(char[] A, int n){
		Arrays.sort(A);//正序排列
		ArrayList<ArrayList<Character>> res = new ArrayList<>();//大集合
		for(int i = (int) (Math.pow(2, n) - 1); i > 0; i--) { //对每个i建立一个集合
			ArrayList<Character> s = new ArrayList<>();
			for(int j = n - 1; j >= 0; j--) {//检查哪个位上的二进制为1,从高位开始检查,高位对应着数组靠后的元素
				if(((i >> j) & 1) == 1){
					s.add(A[j]); 
				}
			}
			res.add(s);
		}
		return res;
	}
}

程序执行结果：

1	[[C, B, A], [C, B], [C, A], [C], [B, A], [B], [A]]

部分和：

给定整数序列a1,a2,…,an,判断是否可以从中选出若干数,使它们的和恰好为k.
1
2
3
4
5
6
> 1≤n≤20
> 
> -10^8≤ai≤10^8
> 
> -10^8≤k≤10^8
>

样例:

输入
1
2
3
4
> n=4
> a={1,2,4,7}
> k=13
>

输出:

1 2	> Yes (13 = 2 + 4 + 7) >

解题思路：

有两种解题方式：

方案1：dfs

方案2：二进制法,解法同上题，子集生成之二进制法。

java解题代码：

方案1代码（dfs）：

import java.util.ArrayList;
import java.util.Scanner;

public class 部分和 {

	static int kk;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int k = sc.nextInt();
		kk = k;//记录k
	    dfs(a, k, 0, new ArrayList<Integer>());
		
	}
	
	public static void dfs(int[] a, int k, int cur, ArrayList<Integer> list) {
		if(k == 0) {
			System.out.print("YES (" + kk + " = " );
			for(int i = 0; i < list.size(); i++) {
				System.out.print(list.get(i) + (i == list.size() - 1 ? "" : " + "));
			}
			System.out.println(")");
			System.exit(0);
		}
		if(k < 0 || cur == a.length) return;
		
		dfs(a, k, cur + 1, list);//不要a[cur]
		
		list.add(a[cur]);
		int index = list.size();
		dfs(a, k - a[cur], cur + 1, list);//要a[cur]
		list.remove(index - 1);//回溯
	}

}

程序运行结果：

4
1 2 4 7
13
YES (13 = 2 + 4 + 7)

方案2（二进制选择）：

package chapter7_递归_DFS_剪枝_回溯;

import java.util.ArrayList;
import java.util.Scanner;

public class 部分和 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int k = sc.nextInt();
	    solve(a, a.length, k);
		
	}

	public static void solve(int[] a, int n,  int k) {
		
		for(int i = (int)(Math.pow(2, n) - 1); i > 0; i--) {
			ArrayList<Integer> list = new ArrayList<>();
			for(int j = 0; j < n; j++) {
				if(((i >> j) & 1) == 1) {
					list.add(a[j]);
				}
			}
			int sum = 0;
			for(int j = 0; j < list.size(); j++) {
				sum += list.get(j);
			}
			if(sum == k) {
				System.out.print("YES (" + k + " = " );
				for(int j = 0; j < list.size(); j++) {
					System.out.print(list.get(j) + (j == list.size() - 1 ? "" : " + "));
				}
				System.out.println(")");
				System.exit(0);
			}
		}
	}
}

程序运行结果：

4
1 2 4 7
11
YES (11 = 4 + 7)

水洼数目：

有一个大小为 NM 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出
园子里总共有多少水洼？（八连通指的是下图中相对 W 的的部分）
***
*W*
***
限制条件

N, M ≤ 100

样例:

输入
N=10, M=12

园子如下图（’W’表示积水， ‘.’表示没有积水）
1
2
3
4
5
6
7
8
9
10
11
12
> 10 12
> W........WW.
> .WWW.....WWW
> ....WW...WW.
> .........WW.
> .........W..
> ..W......W..
> .W.W.....WW.
> W.W.W.....W.
> .W.W......W.
> ..W.......W.
>

输出
1
2
> 3
>

解题思路:

通过DFS来消除一个水洼。循环执行DFS。最后统计消掉的数量。

Java代码示例：

import java.util.Scanner;

public class 水洼数目 {

	private static int n;
	private static int m;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    n = sc.nextInt();
	    m = sc.nextInt();
	    char[][] a = new char[n][];
	    for (int i = 0; i < n; i++) {
	      a[i] = sc.next().toCharArray();
	    }
		int count = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(a[i][j] == 'W') {
					dfs(a, i, j);//消除一个水洼
					count++;
				}
			}
		}
		System.out.println(count);
	}

	public static void dfs(char[][] a, int i, int j) {
		a[i][j] = '.'; //将水抽干，防止再次递归回来
		//判断（x,y）周围的8个点
		for(int x = -1; x < 2; x++) { //-1 0 1
			for(int y = -1; y < 2; y++) {  //-1 0 1
				if(x == 0 && y == 0) continue; //排除自身
				//判断是否是边界的点
				if(i+x >= 0 && i+x <= n-1 && j+y >= 0 && j+y <= m-1) {
					if(a[i + x][j + y] == 'W') {
						dfs(a, i + x, j + y);
					}
				}
			}
		}
		
	}
}

程序运行结果：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W. //输入
count = 3 //输出

回溯：

递归调用代表开启一个分支，如果希望这个分支返回后某些数据恢复到复制开启前的状态以便重新开始，就要使用回溯技巧。
例如：全排列的交换法，数独，部分和，用到了回溯。

剪枝：

深搜时，如已明确从当前状态无论如何转移都不会存在更优解，就应该中断往下的继续搜索，这种方法称为剪枝。
数独里面有剪枝。
部分和里面有剪枝。

n皇后问题：

请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子，

使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。

给定一个int n，请返回方法数，保证n小于等于15

解题思路：

1
2

java代码示例：

import java.util.Scanner;

public class n皇后问题 {
	static int count;
	static int[] rec; //记录下标
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		rec = new int[n];
		dfs(0);
		System.out.println(count);
	}

	public static void dfs(int row) {
		if(row == rec.length) {
			count++;
			return;
		}
		//依次尝试在某列上放一个皇后
		for(int col = 0; col < rec.length; col++) {
			if(check(col, row)) {//检验这个皇后是否和之前已经放置的皇后有冲突
				rec[row] = col; //标记
				dfs(row + 1);//继续找下一行
				//rec[row] = 0; //恢复原状，这种解法这里是否恢复状态都行
			}
		}
	}

	//检验这个皇后是否和之前已经放置的皇后有冲突
	private static boolean check(int col, int row) {
		for(int i = 0; i < row; i++) {
			if(col == rec[i] || row + col == rec[i] + i ||  col - row == rec[i] - i) {
				return false;
			}
		}
		return true;
	}
}

程序运行结果：

1 2	8 //输入 92 //输出

素数环：

输入正整数n，对1-n进行排列，使得相邻两个数之和均为素数，

输出时从整数1开始，逆时针排列。同一个环应恰好输出一次。

n<=16
*

如输入：6

输出：

1 4 3 2 5 6

1 6 5 2 3 4

java代码示例:

import java.util.Scanner;

public class 素数环 {
	static int[] rec;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		rec = new int[n];
		rec[0] = 1;
		sc.close();
		dfs(1);
	}
	
	public static void dfs(int cur) {
		//填到末尾，要首尾相加为素数，才算成功
		if(cur == rec.length && isP(rec[0] + rec[rec.length - 1])) {
			print(rec);
			return;
		}
		//尝试用每个数字填
		for(int i = 2; i <= rec.length; i++) {
			if(check(cur, i)) {
				//试着将i放在cur位置，往前走一步
				rec[cur] = i;
				dfs(cur + 1);
				rec[cur] = 0;//回溯 不回溯也不会影响，因为不影响check
			}
		}
	}

	//打印数组
	private static void print(int[] r) {
		for(int i = 0; i < r.length; i++) {
			System.out.print(rec[i] + (i == rec.length - 1 ? "" : " "));
		}
		System.out.println();
	}

	//判断是否是素数
	private static boolean isP(int num) {
		for(int i = 2; i * i <= num; i++){
			if(num % i == 0) return false;
		}
		return true;
	}

	//判断i是否出现过，以及i + rec[cur-1]的和是否是素数
	private static boolean check(int cur, int i) {
		for(int e : rec) {
			if((e == i) || !isP(rec[cur - 1] + i)){
				return false;
			}
		}
		return true;
	}
}

程序运行结果：

1
2
3

6 //输入
1 4 3 2 5 6 //输出
1 6 5 2 3 4

困难的数：

问题描述:如果一个字符串包含两个相邻的重复子串，则称它为容易的串，其他串称为困难的串,

如:BB，ABCDACABCAB,ABCDABCD都是容易的，A,AB,ABA,D,DC,ABDAB,CBABCBA都是困难的。

输入正整数n,L，输出由前L个字符(大写英文字母)组成的，字典序第n小的困难的串。
例如，当L=3时，前7个困难的串分别为:
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定为4的话,输出ABAC

Java代码示例：

import java.util.Scanner;

public class 困难的串 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();//输出前n个困难的串
		int l = sc.nextInt();//前l个大写字符
		dfs(l, n, "");
	}

	static int count;
	
	public static void dfs(int l, int n, String prefix) {
		//尝试在prefix后追加一个字符
		for(char i = 'A'; i < 'A' + l; i++) {
			if(isHard(prefix, i)) {//是困难的串，就组和起来输出。
				String x = prefix + i;
				System.out.println(x);
				count++; //计数
				if(count == n) {
					System.exit(0);
				}
				dfs(l, n, x);
			}
		}
	}

	/**
	 * 判断prefix + i是否是一个困难的串
	 * 1.遍历所有长度为偶数的子串，看是否对称
	 * 例如； ABA B  先比较 A 和 B，再比较 AB 和 AB
	 * 2.prefix是一个困难的串
	 * @param prefix
	 * @param i
	 * @return 
	 */
	private static boolean isHard(String prefix, char i) {
		int count = 0; //截取的宽度
		for(int j = prefix.length() - 1; j >= 0; j -= 2) {
			final String s1 = prefix.substring(j, j + count + 1);
			final String s2 = prefix.substring(j + count + 1) + i;
			if(s1.equals(s2)) {
				return false;
			}
			count++;
		}
		return true;
	}
}

程序运行结果：

5 4 //输入
A  //输出
AB
ABA
ABAC
ABACA

小结：

有一类问题，有明确的递推形式，比较容易用迭代形式实现，用递归也有较为明确的层数和宽度。

例如：走楼梯、走方格、硬币表示、括号组和、子集、全排列
有一类问题，解的空间很大（往往是阶乘级别的），要在所有可能性中找到答案，只能进行试探，尝试往前走一步，走不通就再退回来，这就是dfs + 回溯 + 剪枝。
对这类问题的优化，越早剪越好，但这很难。如素数环