第三章
枚举
枚举，暴力的一种算法，典型利用”计算机算力大大高于人力”这件事的做法
枚举，顾名思义：有序的尝试每一种可能
在书里，枚举被单独列为一章，不过每一节都是各种花式实战
因此我只想用一个MD笔记来记录它
鬼畜奥数题
我们现在有一道奥数题，要求使用1-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
| #include <stdio.h>
int main(){
int a,b,c,d,e,f,g,h,i = 0 ;
int total = 0 ;
for(a=1;a<=9;a++)
for(b=1;b<=9;b++)
for(c=1;c<=9;c++)
for(d=1;d<=9;d++)
for(e=1;e<=9;e++)
for(f=1;f<=9;f++)
for(g=1;g<=9;g++)
for(h=1;h<=9;h++)
for(i=1;i<=9;i++){
if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h && a!=i &&
b!=c && b!=d && b!=e && b!=f && b!=g && b!=h && b!=i &&
c!=d && c!=e && c!=f && c!=g && c!=h && c!=i &&
d!=e && d!=f && d!=g && d!=h && d!=i &&
e!=f && e!=g && e!=h && e!=i &&
f!=g && f!=h && e!=i &&
g!=h && g!=i &&
h!=i ){
if( a*100+b*10+c + d*100+e*10+f == g+100+h*10+i){
total++ ;
printf("%d%d%d + %d%d%d = %d%d%d \n",a,b,c,d,e,f,g,h,i);
}
}
}
}
printf("total = %d",total/2);
getchar(); getchar();
return 0 ;
}
|
至此我们已经初见了枚举的暴力之处，另外在写判断的时候还是很折磨的
“那么有什么办法方便一点呢”，其实可以。当我们利用标记法（见第一章）就可以节省一点代码量
下面给出用标记法的代码:
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
| #include<stdio.h>
int main(){
int a[10],i,total = 0 , book[10],sum;
for(a[1]=1;a[1]<=9;a[1]++)
for(a[2]=1;a[2]<=9;a[2]++)
for(a[3]=1;a[3]<=9;a[3]++)
for(a[4]=1;a[4]<=9;a[4]++)
for(a[5]=1;a[5]<=9;a[5]++)
for(a[6]=1;a[6]<=9;a[6]++)
for(a[7]=1;a[7]<=9;a[7]++)
for(a[8]=1;a[8]<=9;a[8]++)
for(a[9]=1;a[9]<=9;a[9]++){
for(i=1;i<=9;i++){
book[i] = 0 ;
}
for(i=1;i<=9;i++){
book[a[i]] = 1;
}
sum = 0 ;
for(i=1;i<=9;i++){
sum+=book[i] ;
}
if(sum == 9){
if(a[1]*100+a[2]*10+a[3] + a[4]+a[5]+a[6] = a[7]a[8]a[9]){
total++;
printf("%d%d%d + %d%d%d = %d%d%d",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
}
}
}
printf("total = %d" , total/2);
getchar(); getchar();
return 0 ;
}
```
除了鬼畜奥数，书中还举了“炸弹人”和“火柴棍等式”两个例子
但是枚举的思想是一样的，这里就不一一写出后两者的代码了
### 小结:枚举
那么一般而言，我们需要怎么完成一次合格的“暴力枚举”呢？
1.分析相关的情况，分析题意
2.列举所有的情况(枚举的核心，这一步就大胆做就好了，都枚举了还考虑超不超时？)
3.在2的基础上(一般而言2是通过循环实现的)，进行条件判断
(比如上面的奥数题，就是检查“各个数不相等”和“等式成立”两个条件)
4.如果题目有多个要求，重复2-3步，直到枚举完所有要求
当然，暴力枚举的缺点很明显：时间与内存，因此很多时候不是枚举就完事了
需要带着脑子枚举，有的时候还要利用其它算法优化枚举，不过这就是后话了
# 第四章(上)
## 深度优先搜索 Depth First Search DFS
深度优先是比较基础的一种方法，还有一种是它的兄弟广度优先
**深度优先**顾名思义：先深入搜索到一种情况的"底部"（原谅我用了这么抽象的词），然后再返回搜索其它情况
### 例题
我们依旧举例说明，比如我们现在想要在A,B,C三个箱子中放入1,2,3三张牌，想知道一个有多少种情况
### 循环举穷
首先我们一步步尝试每一次，每一个箱子中的放牌情况
我们约定，对于每个箱子，我们都优先放入1，然后是2，最后是3
当然，如果手上一张牌都没有，也就说明某种情况被列举完了
我们用一个数组a代表箱子，step代表第step个箱子，而i代表牌
我们利用下面这个循环来进行举穷
```C
for(i = 1;i<=n:i++ ){
a[step] = i ;
}
|
另外，一张牌只能用一次，因此我们还要加入一个标记数组book
我们约定： book[i]= 0 代表牌还在手上，=1代表用掉了
所以，我们能把代码更新为：
1
2
3
4
5
6
| for(i = 1;i<=n:i++ ){
if(book[i] == 0 ){
a[step] = i ;
book[i] = i ;
}
}
|
方法与递归
我们观察整体的解法已经上述的举穷，不难发现：我们想要的搜索，实质上就是不断使用上面的方法
所以，我们处理每个盒子的方法都是一样的，我们之间把上述代码变成方法
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
| void dfs(int step){
for(i = 1;i<=n:i++ ){
if(book[i] == 0 ){
a[step] = i ;
book[i] = i ;
}
}
return ;
}
```
我们不断按顺序处理下去，每次都在方法中调用方法自身并把参数加一，我们把这样的做法叫**递归**
另外，每一个箱子尝试之后，记得收回牌
>事实上，开始“收牌”就意味着某一次的情况已经被举完了
```C
void dfs(int step){
for(i = 1;i<=n:i++ ){
if(book[i] == 0 ){
a[step] = i ;
book[i] = i ;
dfs(step+1);
book[i] = 0 ;
}
}
return ;
}
|
收尾
那么我们的搜索什么时候是个头呢，也就是我们搜到第n+1个盒子的时候
（因为卡牌数量和盒子是对应的，循环中n代表有几张牌）
所以，处理到第n+1个盒子时，我们就打印出放法，然后return
P.S 不return就死循环了
完整的方法代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void dfs(int step){
if(step == n+1){
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return ;
}
for(i = 1;i<=n:i++ ){
if(book[i] == 0 ){
a[step] = i ;
book[i] = i ;
dfs(step+1);
book[i] = 0 ;
}
}
return ;
}
|
完整代码
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
| #incluide <stdio.h>
int a[10],book[10],n ;
void dfs(int step){
if(step == n+1){
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
return ;
}
for(i = 1;i<=n:i++ ){
if(book[i] == 0 ){
a[step] = i ;
book[i] = i ;
dfs(step+1);
book[i] = 0 ;
}
}
return ;
}
int main(){
scanf("%d",&n);
dfs(1);
getchar();getchar();
return 0 ;
}
```
### 小结
理解深度优先搜索的关键在于解决**当下该如何做**以及**下一步如何做**的内容
而“下一步如何做”往往可以利用循环或递归解决
我们可以把深度优先算法的模型概括为：
```C
void dfs(int step){
判断边界
尝试每一种可能 for(i=1;i<=n;i++)
{
继续下一步做啥 dfs(step+1) ;
}
返回
}
|
本篇MD记录了深度优先算法最基本的运用，下一篇我们会尝试在更实际的地方运用它：地图搜索
深度优先算法————迷宫
我们尝试把深度优先算法应用到迷宫求解路径中去
实质上，很多搜索算法都是为这种事情服务的。
另外在寻路方面还有一位大佬，那就是A*，这是后话了
例题
我们假设迷宫由n行m列的格子组成，每个格子要么是空地要么是障碍物
设我们的终点在(p,q)，而起点在(1,1)，寻找两点之间的最短路径
(设n,m均小于50)
思路
首先明确人和计算机是不一样，我们最重要的就是找一个通用的搜索法，然后一直用它直到结束
我们需要约定一个顺序进行搜索，并且它是可以运用于每一个格子的
我们不妨这么干：
1.按照右，下，左，上的顺序进行尝试
2.检测：障碍物无法到达，不可越界，不要去走过的点
3.下一点
另外，在每次行动的开始，我们还要判断一件事，那就是是否到达了终点
终点检测
那么这么一个函数只需要三个参数： 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
| void dfs(int x, int y, int step){
if(x==p && y==q){
if(step < min) min = step ;
return ;
}
}
```
#### 顺时针尝试
我们利用一个数组来进行“尝试”的描述
```C
int next[4][2] = { {0,1},
{1,0},
{0,-1},
{-1,0}
```
为什么这么设计呢，我们不妨把这个数组想象为一个向量
对于我们的地图(它实质也是一个二维数组)而言，下标的增加代表向右/向下，减少则是向左/向上
因此在之后的计算中，利用next数组可以迅速得到下一个点的坐标
我们再加上一个for循环来枚举所有可能，就可以得到一个尝试的枚举
```C
for(k=0;k<=3;k++){
tx = x + next[k][0];
ty = y + next[k][1];
}
|
这一部分要是觉得太抽象了，可以画一下next数组的样子来理解，有空的话这里会补图
检测：哪些地方不能去
主要进行下面三个判断：
1.是否越界。根据tx,ty的数值以及地图大小判断即可
2.是否为障碍物。设置一个数组a来登记障碍物
3.是否已经走过。设置一个标记数组book进行标记
可能有人会提出：把走过的路加到障碍物数组中就行了，这种想法很好但实际上却是不方便的
book数组的意义有两个，一是标记走过的路，二是配合尝试计算多个路径（类比一下之前的拿牌和收回牌）
这部分的判断如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| if(tx<1 || tx>n || ty<1 || ty>m ){
continue ;
}
if(a[tx][ty]==0 && book[tx][ty]==0){
book[tx][ty]=1 ;
dfs(tx,ty,step+1) ;
book[tx][ty]=0 ;
}
|
完整代码
#include<stdio.h>
int n,m,p,q,min = 9999999 ;
int a[51][51] , book[51][51] ;
void dfs(int x, int y ,int step){
int next[4][2] = { {0,1}, //向右
{1,0}, //向下
{0,-1}, //向左
{-1,0} //向上
};
int tx,ty,k ;
//判断是否到达目标点
if(x==p && y==q){
//检测是不是新的最小值
if(step < min) min = step ;
return ; //无论如何记得return哦，因为这是我们的base case
}
//枚举走法
for(k=0;k<=3;k++){
tx = x + next[k][0];
ty = y + next[k][1];
if(tx<1 || tx>n || ty<1 || ty>m ){
continue ; //continue就是跳过其它步骤直接进入下一次循环。因为这个点越界了啊
}
if(a[tx][ty]==0 && book[tx][ty]==0){
//如果障碍物数组a和标记数组book都没标记过这个点
book[tx][ty]=1 ; //标记该路径已走过
dfs(tx,ty,step+1) ; //利用递归进行下一步
book[tx][ty]=0 ; //某次尝试的结束，我们要拿回标记
/*
另外，这里就不要continue了，反正都是最后一步了(或者不会执行这一步)
book[tx][ty]=0作为递归部分的下一步，实质上代表了某次尝试的结束
*/
}
}
return ;
}
//主函数
int main(){
int i,j,startx,starty;
//读入相关数值
scanf("%d %d",&n,&m) ; //地图大小
//读入障碍物
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d" , &a[i][j]) ;
}
}
//读入起点和终点
scanf("%d %d %d %d",&startx,&starty,&p,&q);
//开始设置
book[startx][starty] = 1;
//开始搜索
dfs(startx,starty,0) ;
//输出最短步数
printf("%d" , min);
getchar();getchar();
return 0 ;
}
