参考《算法竞赛进阶指南》、AcWing题库

深度优先搜索

深度优先搜索 (DFS, Depth First Search), 顾名思义, 就是按照深度优先的顺序对 “问题状态空间” 进行搜索的算法。在基本算法中, 我们多次把一个问题的求解看作对问题状态空间的遍历与映射。我们可以进一步把 “问题空间” 类比为一张图, 其中的状态类比为节点, 状态之间的联系与可达性就用图中的边来表示, 那么使用深度优先搜索算法求解问题, 就相当于在一张图上进行深度优先遍历。

深度优先搜索与 “递归” 和 “栈” 密切相关。我们倾向于认为 “递归” 是与递推相对的一种单纯的遍历方法, 除了搜索之外, 还有许多算法都可以用递归实现。而 “深搜” 是一类包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称。

在研究深度优先搜索算法之前, 我们先来定义该过程产生的 “搜索树” 结构。在对图进行深度优先遍历处于点 xx 时, 对于某些边 (x,y)(x, y) , yy 是一个尚未访问过的节点, 程序从 xx 成功进入了更深层的对 yy 的递归; 对于另外的一些边 (x,y)(x, y) , yy 已经被访问过, 从而程序继续考虑其他分支。我们称所有点 (问题空间中的状态) 与成功发生递归的边 (访问两个状态之间的移动) 构成的树为一棵 “搜索树”。整个深搜算法就是基于该搜索树完成的一一为了避免重复访问, 我们对状态进行记录和检索; 为了使程序更加高效, 我们提前剪除搜索树上不可能是答案的子树和分支, 不去进行遍历。

我们在前缀和与差分中使用递归实现的指数型、排列型和组合型枚举, 其实就是深搜的三种最简单的形式。与之相关的子集和问题、全排列问题、N 皇后问题等都是可以用深搜求解的经典 NPC 问题。我们先通过几道更加综合性的例题直观地感受一下深度优先搜索算法。后面我们将进一步系统地讨论各类剪枝技巧。

165. 小猫爬山

翰翰和达达饲养了 NN 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 WW，而 NN 只小猫的重量分别是 C1、C2……CNC_1、C_2……C_N。

当然，每辆缆车上的小猫的重量之和不能超过 WW。

每租用一辆缆车，翰翰和达达就要付 11 美元，所以他们想知道，最少需要付多少美元才能把这 NN 只小猫都运送下山？

输入格式

第 11 行：包含两个用空格隔开的整数，NN 和 WW。

第 2..N+12..N+1 行：每行一个整数，其中第 i+1i+1 行的整数表示第 ii 只小猫的重量 CiC_i。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

1≤N≤181 \le N \le 18,
1≤Ci≤W≤1081 \le C_i \le W \le 10^8

输入样例：

1
2
3
4
5
6
5 1996
1
2
1994
12
29

输出样例：

1
2

算法分析

可以使用深度优先搜索算法解决本题。在搜索的过程中，我们可以尝试依次把每一只小猫分配到一辆已经租用的缆车上，或者新租一辆缆车安置这只小猫。于是，我们实时关心的状态有：已经运送的小猫有多少只，已经租用的缆车有多少辆，每辆缆车上当前搭载的小猫重量之和。

编写函数 dfs(now, cnt) 处理第 now 只小猫的分配过程 (前 now - 1 只已经装载), 并且目前已经租用了 cntc n t 辆缆车。对于已经租用的这 cntc n t 辆缆车的当前搭载量, 我们使用一个全局数组 cab[  ]c a b[\;] 来记录。

now, cnt 和 cab 数组共同标识着问题状态空间所类比的 “图” 中的一个 “节 点” 。在这个 “节点” 上, 我们至多有 cnt+1c n t+1 个可能的分支:

  1. 尝试把第 now 只小猫分配到已经租用的第 i(1≤i≤cnt)i(1 \leq i \leq c n t) 辆呰车上。如果第 ii 辆缆车还装得下, 我们就在 cab[i]c a b[i] 中累加 Cnow C_{\text {now }}, 然后递归 dfs(\mathrm{dfs}( now +1,cnt)+1, c n t) 。
  2. 尝试新租一辆缆车来安置这只小猫, 也就是令 cab[cnt+1]=Cnow c a b[c n t+1]=C_{\text {now }}, 然后递归 dfs (( now+1,cnt+1now +1, c n t+1) 。

当 now =N+1=N+1 时, 说明搜索到了递归边界, 此时就可以用 cntc n t 更新答案。 为了让搜索过程更加高效, 我们可以加入一个很显然的优化: 如果在搜索的任何时刻发现 cntc n t 已经大于或等于已经搜到的答案, 那么当前分支就可以立即回溯了。另外, 重量较大的小猫显然比重量较轻的小猫更 “难” 运送, 我们还可以在整个搜索前把小猫按照重量递减排序, 优先搜索重量较大的小猫, 减少搜索树 “分支” 的数量。读者可以比较加入这两条优化前后, 程序运行时间的差异。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[20], cab[20], n, w, ans;
void dfs(int now, int cnt) {
	if (cnt >= ans) return;
	if (now == n+1) {
		ans = min(ans, cnt);
		return;
	}
	for (int i = 1; i <= cnt; i++) {  // 分配到已租用缆车
		if (cab[i] + c[now] <= w) {   // 能装下
			cab[i] += c[now];
			dfs(now+1, cnt);
			cab[i] -= c[now];         // 还原现场
		}
	}
	cab[cnt+1] = c[now];
	dfs(now+1, cnt+1);
	cab[cnt+1] = 0;
}
int main() {
	cin >> n >> w;
	for (int i = 1; i <= n; i++) cin >> c[i];
	sort(c + 1, c + n + 1);
	reverse(c + 1, c + n + 1);
	ans = n;    // 最多用n辆缆车，每只猫一辆
	dfs(1, 0);  // 搜索入口
	cout << ans << endl;
}

Solution

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
//30ms
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 25;

int n, W, ans;
int c[N];
int sum[N];

void dfs(int cnt, int now){
  if (cnt >= ans) return;
  if (now == n + 1) {
    ans = cnt;
    return;
  }
  
  for (int i = 1; i <= cnt; ++i) {
    if (sum[i] + c[now] <= W) {
      sum[i] += c[now];
      dfs(cnt, now + 1);
      sum[i] -= c[now];
    }
  }
  
  sum[cnt + 1] += c[now];
  dfs(cnt + 1, now + 1);
  sum[cnt + 1] -= c[now];
}

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; ++i) cin >> c[i];
  
  sort(c + 1, c + 1 + n, greater<int>());
  
  ans = n;
  
  dfs(1, 1);
  
  cout << ans;
}
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
//160ms
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 25;

int n, W, ans;
int c[N];
int sum[N];
bool used[N];

void dfs(int cnt, int now, int start){
  if (now >= ans) return;
  if (cnt == n) {
    ans = now;
    return;
  }
  
  bool flag = true;
  for (int i = start; i <= n; ++i) {
    if (!used[i] && sum[now] + c[i] <= W) {
      used[i] = true;
      sum[now] += c[i];
      dfs(cnt + 1, now, i + 1);
      sum[now] -= c[i];
      used[i] = false;
      flag = false;
      if (start == 1) return;
    }
  }
  
  if (flag) {
    dfs(cnt, now + 1, 1);
  }
}

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; ++i) cin >> c[i];
  
  sort(c + 1, c + 1 + n, greater<int>());
  
  ans = n;
  
  dfs(0, 1, 1);
  
  cout << ans;
}

166. 数独

数独是一种传统益智游戏，你需要把一个 9×99 \times 9 的数独补充完整，使得图中每行、每列、每个 3×33 \times 3 的九宫格内数字 1∼91 \sim 9 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 8181 个字符，代表数独的 8181 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−91-9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

1
2
3
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

1
2
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

算法分析

数独问题的搜索框架非常简单，我们关心的 “状态” 就是数独的每个位置上填了什么数。在每个状态下，我们找出一个还没有填的位置，检查有哪些合法的数字可以填。这些合法的数字就构成该状态向下继续递归的“分支” 。

搜索边界分为两种： 一是如果所有位置都被填满，就找到了一个解； 二是如果发现某个位置没有能填的合法数字，说明当前分支搜索失败，应该回溯去尝试其他分支。

如下图所示，就是用深度优先搜索算法求解 Sudoku 问题产生的一棵搜索树。

提醒：在任意一个状态下，我们只需要找出 1 个位置，考虑该位置上填什么数（如上图搜索树的根节点只有2 个分支），不需要枚举所有的位置和可填的数字向下递归（因为其他位置在更深的层次会被搜索到）。新手常犯的错误就是重叠、混淆 “层次” 和 “分支”，造成重复遍历若干棵覆盖同一状态空间的搜索树，致使搜索的复杂度大规模增长。

然而, 数独问题的 “搜索树” 规模仍然很大, 直接盲目搜索的效率实在不能接受。试想, 如果是人类来玩数独, 策略一定是先填上 “已经能够唯一确定的位置”, 然后从那些填得比较满、选项比较少的位置实施突破。所以在搜索算法中, 也应该采取类似的策略: 在每个状态下, 从所有未填的位置里选择 “能填的合法数字” 最少的位置, 考虑该位置上填什么数, 作为搜索的分支, 而不是任意找出 1 个位置。

在搜索程序中, 影响时间效率的因素除了搜索树的规模 (影响算法的时间复杂度), 还有在每个状态上记录、检索、更新的开销 (影响程序运行的 “常数” 时间)。我们可以使用位运算来代替数组执行 “对数独各个位置所填数字的记录” 以及 “可填性的检查与统计” 。这就是我们所说的程序 “常数优化” : 具体地说:

  1. 对于每行、每列、每个九宫格, 分别用一个 9 位二进制数 (全局整数变量) 保存哪些数字还可以填。
  2. 对于每个位置, 把它所在行、列、九宫格的 3 个二进制数做位与(&)运算, 就可以得到该位置能填哪些数, 用 lowbit 运算就可以把能填的数字取出 (在位运算中已经探讨了这一技巧)。
  3. 当一个位置填上某个数后, 把该位置所在的行、列、九宫格记录的二进制数的对应位改为 0 , 即可更新当前状态; 回溯时改回 1 即可还原现场。

上述算法已经能够快速求解 9∗99 * 9 的数独问题, 并且程序的实现十分简洁。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[10][10];
int row[9], col[9], grid[9], cnt[512], num[512], tot;

inline int g(int x, int y) {
	return ((x / 3) * 3) + (y / 3);
}

inline void flip(int x, int y, int z) {
	row[x] ^= 1 << z;
	col[y] ^= 1 << z;
	grid[g(x, y)] ^= 1 << z;
}

bool dfs(int now) {
	if (now == 0) return 1;
	int temp = 10, x, y;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++) {
			if (str[i][j] != '.') continue;
			int val = row[i] & col[j] & grid[g(i, j)];
			if (!val) return 0;
			if (cnt[val] < temp) {
				temp = cnt[val];
				x = i, y = j;
			}
		}
	int val = row[x] & col[y] & grid[g(x, y)];
	for (; val; val -= val&-val) {
		int z = num[val&-val];
		str[x][y] = '1' + z;
		flip(x, y, z);
		if (dfs(now - 1)) return 1;
		flip(x, y, z);
		str[x][y] = '.';
	}
	return 0;
}

int main() {
	for (int i = 0; i < 1 << 9; i++)
		for (int j = i; j; j -= j&-j) cnt[i]++;
	for (int i = 0; i < 9; i++)
		num[1 << i] = i;
	char s[100];
	while (~scanf("%s", s) && s[0] != 'e') {
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) str[i][j] = s[i * 9 + j];
		for (int i = 0; i < 9; i++) row[i] = col[i] = grid[i] = (1 << 9) - 1;
		tot = 0;
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if (str[i][j] != '.') flip(i, j, str[i][j] - '1');
				else tot++;
		dfs(tot);
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) s[i * 9 + j] = str[i][j];
		puts(s);
	}
}
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
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstring>
#include <iostream>
using namespace std;
char s[81];
int cnt[1<<9], f[1<<9];
int x[9], y[9], z[9], X[81], Y[81];
int gx, gy, gz;

inline void get(int i) {
	gx = X[i];
	gy = Y[i];
	gz = gx / 3 * 3 + gy / 3;
}

void work(int i, int k) {
	get(i);
	x[gx] ^= (1 << k);
	y[gy] ^= (1 << k);
	z[gz] ^= (1 << k);
}

bool dfs(int ans) {
	if (!ans) return 1;
	int k = 10, t;
	for (int i = 0; i < 81; i++)
		if (s[i] == '.') {
			get(i);
			int w = x[gx] & y[gy] & z[gz];
			if (cnt[w] < k) {
				k = cnt[w];
				t = i;
			}
		}
	get(t);
	int w = x[gx] & y[gy] & z[gz];
	while (w) {
		int now = f[w&-w];
		s[t] = now + '1';
		work(t, now);
		if (dfs(ans - 1)) return 1;
		work(t, now);
		s[t] = '.';
		w -= w & -w;
	}
	return 0;
}

void Sudoku() {
	for (int i = 0; i < 9; i++) x[i] = y[i] = z[i] = (1 << 9) - 1;
	int ans = 0;
	for (int i = 0; i < 81; i++)
		if (s[i] != '.') work(i, s[i] - '1');
		else ++ans;
	if (dfs(ans)) for (int i = 0; i < 81; i++) cout << s[i];
	cout << endl;
}

int get_cnt(int i) {
	int ans = 0;
	while (i) {
		++ans;
		i -= (i & -i);
	}
	return ans;
}

int main() {
	for (int i = 0; i < (1 << 9); i++) cnt[i] = get_cnt(i);
	for (int i = 0; i < 9; i++) f[1<<i] = i;
	for (int i = 0; i < 81; i++) {
		X[i] = i / 9;
		Y[i] = i % 9;
	}
	while (cin >> s && s[0] != 'e') Sudoku();
	return 0;
}

通过本节的内容, 读者可能已经发现, 一般搜索解法的基本框架并不难, 但如何减小搜索树的规模并快速遍历搜索树却是一门高深的学问。在剪枝和迭代加深中, 我们就重点研究搜索的优化。我们还会探究 16∗1616 * 16 的数独问题, 进一步提高求解数独的效率。

Solution

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <string>
using namespace std;

const int N = 9, M = 1 << N;

char g[N][N];
int row[N], col[N], cell[N][N];
int ones[M], map[37];
string str;
int cnt;

int lowbit(int x) {// 返回末尾的1
    return x & -x;
}

void draw(int x, int y, int k, bool flag) {
  int t = 1 << k;
  if (flag) g[x][y] = k + '1';
  else g[x][y] = '.';
  row[x] ^= t;
  col[y] ^= t;
  cell[x / 3][y / 3] ^= t;
}

bool dfs(int now) {
  if (now == 0) return true;
  
  //找到“能填的合法数字”最少的位置
  int minv = 10, x, y;
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      if (g[i][j] == '.') {
        int state = row[i] & col[j] & cell[i / 3][j / 3];
        if (state == 0) return false;
        if (ones[state] < minv) {
          minv = ones[state];
          x = i, y = j;
        }
      }
    }
  }
  
  int state = row[x] & col[y] & cell[x / 3][y / 3];
  for (int i = state; i; i -= lowbit(i)) {
    int k = map[lowbit(i) % 37];
    draw(x, y, k, true);
    if (dfs(now - 1)) return true;
    draw(x, y, k, false);
  }
  
  return false;
}

void prework() {
  for (int i = 0; i < 9; ++i) map[(1 << i) % 37] = i;
  
  for (int i = 0; i < 1 << 9; ++i) 
    for (int j = i; j; j -= lowbit(j)) ++ones[i];  
}

void init() {
  // 转为 9*9 的图
  for (int i = 0; i < 9; ++i) 
    for (int j = 0; j < 9; ++j) g[i][j] = str[i * 9 + j]; 
  
  // 初始化标记数组
  for (int i = 0; i < 9; ++i) {
    row[i] = col[i] = (1 << 9) - 1;
    for (int j = 0; j < 9; ++j) {
      cell[i / 3][j / 3] = (1 << 9) - 1;
    }
  }
  
  //计算一共需要填多少个数字，并初始化相应状态
  cnt = 0;
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      if (g[i][j] != '.') {
        int k = g[i][j] - '1';
        draw(i, j, k, true);
      } else {
        ++cnt;
      }
    }
  }
}

void print() {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      cout << g[i][j];
    }
  }
  cout << endl;
}

int main() {
  // 预处理每个状态 1 的个数，即能填的数字个数
  // 预处理 lowbit() 值中的 1 对应的是第几位
  prework(); 

  while (cin >> str, str[0] != 'e') {
    init(); //初始化
    
    dfs(cnt);
    
    print();
  }
}

连通性问题

1112. 迷宫

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗nn * n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

输入格式

第1行是测试数据的组数 kk，后面跟着 kk 组输入。

每组测试数据的第1行是一个正整数 nn，表示迷宫的规模是 n∗nn * n 的。

接下来是一个 n∗nn * n 的矩阵，矩阵中的元素为.或者#。

再接下来一行是 4 个整数 ha,la,hb,lbh_a, l_a, h_b, l_b，描述 AA 处在第 hah_a 行, 第 lal_a 列，BB 处在第 hbh_b 行, 第 lbl_b 列。

注意到 ha,la,hb,lbh_a, l_a, h_b, l_b 全部是从 0 开始计数的。

输出格式

k行，每行输出对应一个输入。

能办到则输出“YES”，否则输出“NO”。

数据范围

1≤n≤1001 \le n \le 100

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

输出样例:

1
2
YES
NO

算法分析

Solution

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

char g[N][N];
bool vis[N][N];
int n;
int xa, ya, xb, yb;

bool dfs(int x, int y) {
  if (g[x][y] == '#') return false; //通过该点不可能到达
  if (x == xb && y == yb) return true; //当前已到达终点，返回true
  
  vis[x][y] = true;
  
  for (int i = 0; i < 4; ++i) {
    int nx = x + dx[i], ny = y + dy[i];
    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
    if (vis[nx][ny]) continue;
    if (dfs(nx, ny)) return true; //通过邻接点能到达终点，返回true
  }
  return false; // 到达不了终点，返回false
}

int main() {
  int k;
  cin >> k;
  while (k--) {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> g[i];

    memset(vis, 0, sizeof vis);
    
    cin >> xa >> ya >> xb >> yb;
    
    if (dfs(xa, ya)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}

1113. 红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 WW 和 HH，分别表示 xx 方向和 yy 方向瓷砖的数量。

在接下来的 HH 行中，每行包括 WW 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤201 \le W,H \le 20

输入样例：

1
2
3
4
5
6
7
8
9
10
11
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例：

1
45

算法分析

Solution

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 25;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
char g[N][N];
bool vis[N][N];

int dfs(int x, int y) { 
  // 进入函数的都是合法点
  int ans = 1;
  vis[x][y] = true;
  for (int i = 0; i < 4; ++i) { // 把不能搜索的情况都在这里一并排除掉
    int a = x + dx[i], b = y + dy[i];
    if (a < 1 || a > n || b < 1 || b > m) continue;
    if (g[a][b] == '#') continue;
    if (vis[a][b]) continue;
    ans += dfs(a, b);
  }
  return ans;
}

int main() {
  while (cin >> m >> n, n || m) {
    int x, y;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        cin >> g[i][j];
        if (g[i][j] == '@') x = i, y = j;
      }
    }
    memset(vis, 0, sizeof vis); //记得要清除标记数组状态
    cout << dfs(x, y) << endl;
  }
}

DFS 搜索顺序

1116. 马走日

马在中国象棋以日字形规则移动。

请编写一段程序，给定 n∗mn*m 大小的棋盘，以及马的初始位置 (x，y)(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入格式

第一行为整数 TT，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,yn,m,x,y。

输出格式

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。

数据范围

1≤T≤91 \le T \le 9,
1≤m,n≤91 \le m,n \le 9,
0≤x≤n−10 \le x \le n-1,
0≤y≤m−10 \le y \le m-1

输入样例：

1
2
1
5 4 0 0

输出样例：

1
32

算法分析

Solution

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
const int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;
bool vis[N][N];
int ans;

void dfs(int x, int y, int cnt) {
  if (++cnt == n * m) ++ans;
  vis[x][y] = true;
  for (int i = 0; i < 8; ++i) {
    int nx = x + dx[i], ny = y + dy[i];
    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (vis[nx][ny]) continue;
    dfs(nx, ny, cnt);
  }
  vis[x][y] = false;
}

int main() {
  int T; 
  cin >> T;
  while (T--) {
    int x, y;
    cin >> n >> m >> x >> y;
    ans = 0;
    memset(vis, 0, sizeof vis);
    dfs(x, y, 0);
    cout << ans << endl;
  }
}

1117. 单词接龙

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 nn 表示单词数，以下 nn 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

数据范围

n≤20n \le 20

输入样例：

1
2
3
4
5
6
7
5
at
touch
cheat
choose
tact
a

输出样例：

1
23

提示

连成的“龙”为 atoucheatactactouchoose。

算法分析

Solution

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
#include <iostream>
using namespace std;

const int N = 25;

int n, ans;
int used[N], comlen[N][N];
string word[N];
char start;

void prework() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k < min(word[i].size(), word[j].size()); ++k) {
        if (word[i].substr(word[i].size() - k) == word[j].substr(0, k)) {
          comlen[i][j] = k;
          break;
        }
      }
    }
  }
}

void dfs(string cur, int last) {
  used[last]++;
  ans = max((int)cur.size(), ans);

  for (int i = 1; i <= n; ++i) {
    int len = comlen[last][i];
    if (len && used[i] < 2) {
      string next = cur + word[i].substr(len);
      dfs(next, i);
    }
  }
  
  used[last]--;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> word[i];
  cin >> start;
  
  prework();
  
  for (int i = 1; i <= n; ++i) 
    if (word[i][0] == start) 
      dfs(word[i], i);

  cout << ans;
}

1118. 分成互质组

给定 nn 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式

第一行是一个正整数 nn。

第二行是 nn 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1≤n≤101 \le n \le 10

输入样例：

1
2
6
14 20 33 117 143 175

输出样例：

1
3

算法分析

Solution

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
#include <iostream>
using namespace std;

const int N = 15;
int n, ans;
int nums[N];
bool used[N];
int g[N][N];

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

bool check(int gid, int idx,int num) {
  auto &cur = g[gid];
  for (int i = 0; i < idx; ++i) 
    if (gcd(cur[i], num) > 1) return false;
  return true;
}
// start 表示从哪个位置开始选择元素【组合套路(定一个遍历顺序)】
// 本质是将排列搜索空间变成组合搜索空间来排除等效冗余
void dfs(int gid, int idx, int start, int cnt) {
  if (gid >= ans) return;
  if (cnt == n) ans = gid;
  
  bool flag = true;
  
  auto &cur = g[gid];
  
  for (int i = start; i < n; ++i) {
    if (!used[i] && check(gid, idx, nums[i])) {
      used[i] = true;
      cur[idx] = nums[i];
      
      dfs(gid, idx + 1, i + 1, cnt + 1);
      
      used[i] = false;
      
      flag = false;
		
	  //固定将第一个数放到新组中，避免搜索冗余	
	  if (start == 0) return;	
    }
  }
  
  if (flag) dfs(gid + 1, 0, 0, cnt);
}


int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> nums[i];
  
  ans = n;
  
  dfs(1, 0, 0, 0);
  
  cout << ans;
}