【蓝桥备战】DFS、BFS

DFS

深度优先搜索。以二叉树为例，只有当前节点不能继续遍历时，才会往回退，否则就继续搜索。
使用栈这种数据结构实现。空间复杂度为O(n)。不具有“最短路径”的性质。
把握两个概念：回溯、剪枝。DFS考虑顺序，类似递归，考虑dfs函数的意义。

全排列数字

使用dfs算法，使用path数组保存结果，使用used数组判断数字是否使用。明确每一层要做的事情：

1. 判断当前数字是否使用，如果没有使用，就使用当前数字。
2. 每次回溯时恢复原状态。
   

import java.util.Scanner;

public class Main {
	static int N = 10;
	//使用path保存全排列数。
	static int path[];
	static boolean used[];
	static int n;
	public static void main(String[] args) {
		Scanner s = new Scanner (System.in);
		n = s.nextInt();
		path = new int [n];
		used = new boolean [n + 1];
		dfs(0);
	}
	static void dfs(int u) {
		//如果u是n，说明当前已经排好了n个数字，输出即可。
		if(u == n) {
			for(int i = 0;i<n;i++) {
				System.out.print(path[i] + " ");
			}
			System.out.println();
		}
		//寻找当前没有使用的数字。
		for(int i = 1;i<=n;i++) {
			//如果当前数字没有使用，则使用当前数字，继续深度搜索。
			if(!used[i]) {
				path[u] = i;
				used[i] = true;
				dfs(u + 1);
				used[i] = false;
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

八皇后问题

解法一：类似全排列的思想。**按行进行dfs。**不用考虑同一行的问题。

import java.util.Scanner;

public class Main {
	static int N = 20;
	static char grp[][];
	static int n;
	static boolean col[] = new boolean [N];
	static boolean dg[] = new boolean [N];
	static boolean udg[] = new boolean [N];
	public static void main(String[] args) {
		Scanner s = new Scanner (System.in);
		n = s.nextInt();
		grp  = new char [n][n];
		for(int i = 0;i<n;i++) {
			for(int j = 0;j<n;j++) {
				grp[i][j] = '.';
			}
		}
		dfs(0);
		}
		
	static void dfs(int row) {
		if(row == n) {
			for(int i = 0;i<n;i++) {
				System.out.println(grp[i]);
			}
			System.out.println();
			return;
		}
		
		//判断该行的每列位置是否合法。合法——不在同一列、同一斜线、同一直线。
		for(int coll = 0;coll<n;coll++) {
			//每一条对角线对应唯一截距：反对角线：y = x + b  截距：b = y - x
			//						对角线：y = -x + b 截距：b = y + x
			if(!col[coll] && !dg[row + coll] && !udg[n + coll - row]) {
				grp[row][coll] = 'Q';
				col[coll] = dg[row + coll] = udg[n + coll - row] =  true;
				dfs(row + 1);
				grp[row][coll] = '.';
				col[coll] = dg[row + coll] = udg[n + coll - row] =  false;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

解法二：把每一个格子都分为两种状态【放（满足条件时）/不放（不需要条件）】。
当满足x为最后的一行并且皇后数量等于n时，才会输出答案。

import java.util.Scanner;

public class Main {
	static int N = 20;
	static int n;
	static char grp[][];
	static boolean row [] = new boolean [N];
	static boolean colum [] = new boolean [N];
	static boolean bg []  = new boolean [N];
	static boolean ubg []  = new boolean [N];
	public static void main(String[] args) {
		Scanner s = new Scanner (System.in);
		n = s.nextInt();
		grp = new char [n][n];
		dfs(0,0,0);
	}
	static void dfs(int x,int y,int s) {
		//当前行全部走了一遍，跳到下一行。
		if(y == n) {
			x ++;
			y = 0;
		}
		//走到了最后一行
		if(x == n) {
			//此时的皇后数等于n的数量，即为符合条件
			if(s == n) {
				for(int i = 0;i<n;i++) {
					System.out.println(grp[i]);
				}
				System.out.println();
			}
			return ;
		}
		
		//当前格子不放皇后
		grp[x][y] = '.';
		dfs(x,y + 1,s);
		
		//当前格子放皇后
		if(!row [x] && !colum[y] && !bg[x + y] && !ubg[n + x - y]) {
			row[x] = colum[y] = bg[x + y] = ubg[n + x - y] = true;
			grp[x][y] = 'Q';
			dfs(x,y + 1,s + 1);
			row[x] = colum[y] = bg[x + y] = ubg[n + x - y] = false;
			grp[x][y] = '.';
		}
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

BFS

广度优先搜索。以二叉树为例，类似于二叉树的层序遍历。
数据结构：使用队列。空间O(2^n)。具有“最短路径”的性质。

走迷宫

该题的边权都是1，所以可以使用BFS，思路如下：
每次从迷宫左上角开始搜索，如果可以走就做标记，并且将可以走的点放入队列，并将当前路径步数加一。
PS：最先走到的一定就是迷宫最短的路径,后面走过来的会发现d[n - 1][m - 1]已经不为0。

{
	static int n,m;
	static int map [][];
	//保存路径步数。
	static int d [][];
	public static void main(String[] args) throws IOException {
		 InputStreamReader in = new InputStreamReader(System.in);
	        BufferedReader br = new BufferedReader(in);
	        String[] nums = br.readLine().split(" ");

	        n = Integer.parseInt(nums[0]);
	        m = Integer.parseInt(nums[1]);

	        map = new int[n][m];
	        d = new int[n][m];
	        for(int i = 0; i < n; i++) {
	            String[] inputs = br.readLine().split(" ");
	            for (int j = 0; j < m; j++) {
	                map[i][j] = Integer.parseInt(inputs[j]);
	            }
	        }
	        System.out.println(dfs());
	        
	}
	static int dfs() {
		Queue<int [][]> q = new LinkedList<>();
		q.offer(new int[][] {{0,0}});
		d[0][0] = 0;
		//上下左右顺序。
		int []dx  = {-1,1,0,0};
		int []dy =  {0,0,-1,1};
		
		while(!q.isEmpty()) {
			//得到当前点的位置。
			int [][]pair = q.poll();
			int pair_x = pair[0][0];
			int pair_y = pair[0][1];
			
			//BFS寻找当前点的四周所有点。
			for(int i = 0;i<4;i++) {
				int x = pair_x + dx[i];
				int y = pair_y + dy[i];
				if(x >=0 && x < n && y>=0 && y<m && map[x][y] == 0 && d[x][y] == 0) {
					//放入队列。
					q.offer(new int [][] {{x,y}});
					//路径加一。
					d[x][y] = d[pair_x][pair_y] + 1;
					
				}
			}
			
		}
		return d[n - 1][m - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

八数码

public class Main {
	static String start = ""; 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String []str = br.readLine().split(" ");
		for(int i = 0;i<9;i++) {
			start += str[i];
		}
		System.out.println(dfs(start));
		
	}
	
	static int dfs(String start) {
		Queue<String> q = new LinkedList<>();
		q.offer(start);
		//表示当前状态String到原状态start的距离为Integer。
		HashMap<String,Integer> map = new HashMap<>();
		map.put(start, 0);
		String end = "12345678x";
		
		while(!q.isEmpty()) {
			start = q.poll();
			int distance = map.get(start);
			if(start.equals(end)) {
				return distance;
			}
			
			int [] dx = {0,0,-1,1};
			int [] dy = {-1,1,0,0};
			//index表示x在start中的位置。
			int index = start.indexOf("x");
			//a,b表示x在3x3网格中的下标。
			int a = index / 3,b = index % 3;
			for(int i = 0;i < 4;i++) {
				//x,y表示x在3x3网格中经过变换后的下标。
				int x = a + dx[i],y = b + dy[i];
				if(x >=0 && x < 3 && y >=0 && y < 3) {
					//index01表示x经过变换后，在String中的下标。
					int index01 = x * 3 + y;
					start = swap(start,index01,index);
					//表示没到过这种状态。
					if(!map.containsKey(start)) {
						q.offer(start);
						//变换后的start，存入map，并将步数加一。
						map.put(start, distance + 1);
					}
					//将start回复原样。
					start = swap(start,index01,index);
				}
			}
			
		}
		
		return -1;
	}
	
	static String swap(String s,int a,int b){
        StringBuffer sb = new StringBuffer(s);
        char temp = sb.charAt(a);
        sb.setCharAt(a,sb.charAt(b));
        sb.setCharAt(b,temp);
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64