DFS

为对一组数进行 全排列 深度优先搜索

#include<stdio.h> int a[10], book[10],n; void dfs(int step) { int i; if (step == n + 1) //如果已经选择完毕 { //则打印，所选数据 for (i = 1; i <= n; i++) printf("%d ", a[i]); printf("\n"); return; //一定要立即return，不然就会无限制地运行下去 } for (i = 1; i <= n; i++) //选择数 { if (book[i] == 0) //如果这个数是可选的 { a[step] = i; //第step个位置，选择的数i book[i] = 1; //因为上面a[]已选，则把这个i标记为不可选 dfs(step + 1); //选择下一个数 book[i] = 0; //将上面选择的数标记为可选，为下一次选数做准备 } } return; } int main() { scanf("%d", &n); dfs(1); return 0; }

深度优先搜索的关键在于解决 “当下该如何做” 。 至于下一步怎么做是和 “当下怎么做” 是一样的

深度优先搜索的基本模型：

void dfs(int step) { 判断边界，并进行一些操作 尝试每一种可能 for (i = 1; i <= n; i++) { 继续下一步 dfs(step + 1); } 返回 }

每一种尝试就是一种扩展

---

题目1

[ ][ ][ ]+[ ][ ][ ]=[ ][ ][ ] 找九个互不相同的数，使上式成立

#include<stdio.h> int a[10], book[10], total = 0; void dfs(int step) { int i; if (step == 10) //如果选择完毕 { if (a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6] == a[7] * 100 + a[8] * 10 + a[9]) { total++; printf("%d%d%d+%d%d%d+%d%d%d\n", a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]); } return; //返回之前的一步，最近调用的地方 } //此刻进行第step的选择 for (i = 1; i <= 9; i++) //按照1/2/3···牌的顺序选择 { if (book[i] == 0) //判断i这个数是否还可以被选 { a[step] = i; //选择i book[i] = 1; //表示i已经被选了，不能再选了 dfs(step + 1); //进行下一选择 book[i] = 0; //把刚刚选的标记删除，进行下一次尝试 } } return; } int main() { dfs(1); //对第一个数进行选择 printf("total=%d", total / 2); //因为会有相同的，比如A+B=C和B+A=C相同 return 0; }

这个代码中最为关键的还是dfs那一部分。 dfs的思想方法 简直牛逼的不行

走迷宫

主要思想 深度优先，先走一边，然后一直尝试，直到走不通了，就层层回溯，回到最初的位置，然后换方向走

就是先判断这个点是不是想要走到的点 如果不是，则进行走到下一个点 并递归调用dfs，以对下一个点进行分析，操作

//当前点的x，y坐标，以及已经走过的步数step void dfs(int x, int y, int step) { //判断是否找到了 if (x == p && y == q) //如果找到了 { if (step < min) //看是不是比最小的还要小 min = step; return; //这里的返回很重要 } //如果没有找到，则找出下一步可以走的地方 int next[4][2] = { {0,1}, //向右走 {1,0}, //向下走 {0,-1}, //向左走 {-1,0} }; //向上走 for (k = 0; i < 4; k++) { tx = x + next[k][0]; //下一步的坐标 ty = y + next[k][1]; 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; //尝试结束，也就是退到了这个点的上一个位置 } } return; }

完整代码：

#include<stdio.h> int n, m, p, q, min = 999999999; int a[51][51], book[51][51]; //当前点的x，y坐标，以及已经走过的步数step void dfs(int x, int y, int step) { //判断是否找到了 int tx, ty, k; if (x == p && y == q) //如果找到了 { if (step < min) //看是不是比最小的还要小 min = step; return; //这里的返回很重要 } //如果没有找到，则找出下一步可以走的地方 int next[4][2] = { {0,1}, //向右走 {1,0}, //向下走 {0,-1}, //向左走 {-1,0} }; //向上走 for (k = 0; k < 4; k++) { tx = x + next[k][0]; //下一步的坐标 ty = y + next[k][1]; 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; //尝试结束，也就是退到了这个点的上一个位置 } } 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); return 0; }

BFS

广度优先搜索 宽度优先搜索

走迷宫

通过一层一层的扩展，来找到想要找到的出路 扩展时每发现一个点就把这个点加入到队列中，直到走到出路为止

核心思想： 利用队列，实现层层扩展

核心代码：

while (head < tail) //当队列不为空的时候循环 { //枚举四个方向 for (k = 0; k < 4; k++) { tx = que[head].x + next[k][0]; //下一个点是从head扩展出来的 ty = que[head].y + next[k][1]; //判断是否越界 if (tx<1 || tx>n || ty<1 || ty>m) continue; //判断是否是障碍物或者已经走过了 if (a[tx][ty] == 0 && book[tx][ty] == 0) { //把这个点标记为已走 //BFS中每个点只入队一次，因此，book一旦标记，就不再还原 book[tx][ty] = 1; //将走到的点插入到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; //因为这个点是从head扩展出来的，因此父亲就是head que[tail].s = que[head].s + 1; tail++; } if (tx == p && ty == q)//如果到达终点了，直接跳出 { flag = 1; break; } } if (flag == 1) break; head++; //当一个点的扩展结束了，head++才能对后面的点再扩展 } #include<stdio.h> struct node { int x; //横坐标 int y; //纵坐标 int f; //父亲在队列中的编号，这个是为输出路径而准备的 int s; //步数 }; int main() { int i, j, k, n, m; node que[2501]; //因为地图大小不超过50*50，因此队列扩展不会超过2500 int head, tail; //队首，队尾 int a[51][51] = { 0 }; //地图 int book[51][51] = { 0 }; //book的作用是记录哪些点已经在队列中，防止一个点被重复扩展，并全部初始化为0 int next[4][2] = { {0,1}, //向右走 {1,0}, //向下走 {0,-1}, //向左走 {-1,0} }; //向上走 int startx, starty; //开始的位置的横纵坐标 int p, q; int tx, ty; //下一个点的横纵坐标 int flag; 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); //最开始的时候需要进行队列初始化，即将队列设置为空 head = 1; tail = 1; //在队列中设置开始时位置坐标以及路径长度 que[tail].x = startx; que[tail].y = starty; que[tail].s = 0; que[tail].f = 0; tail++; book[startx][starty] = 1; flag = 0; //用来记录是否到达目标点，0表示未到，1表示到达 while (head < tail) //当队列不为空的时候循环 { //枚举四个方向 for (k = 0; k < 4; k++) { tx = que[head].x + next[k][0]; //下一个点是从head扩展出来的 ty = que[head].y + next[k][1]; //判断是否越界 if (tx<1 || tx>n || ty<1 || ty>m) continue; //判断是否是障碍物或者已经走过了 if (a[tx][ty] == 0 && book[tx][ty] == 0) { //把这个点标记为已走 //BFS中每个点只入队一次，因此，book一旦标记，就不再还原 book[tx][ty] = 1; //将走到的点插入到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; //因为这个点是从head扩展出来的，因此父亲就是head que[tail].s = que[head].s + 1; tail++; } if (tx == p && ty == q)//如果到达终点了，直接跳出 { flag = 1; break; } } if (flag == 1) break; head++; //当一个点的扩展结束了，head++才能对后面的点再扩展 } //打印队列中末尾最后一个点的步数(这时候就是到达终点的点) printf("%d", que[tail - 1].s); //tail指向的队列中最后一个元素的下一个位置。因此需要减1 return 0; }

炸弹人

BFS大致的模板

while (head < tail) { for (k = 0; k < 4; k++) { tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; if (tx<1 || tx>n || ty<1 || ty>m) continue; if (a[tx][ty] == '.' && book[tx][ty] == 0) { book[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; //在这里进行你先要的操作 tail++; } } head++; }

DFS 这个与为了找到终点是不一样的 这个是为遍历图中的每一个点 因此，需要的将所有的点都做一个标记 而且不能清除这个标记，不然没有办法知道，是否遍历完所有的点

void dfs(int x, int y) { //操作 for (k = 0; k < 4; k++) { tx = x + next[k][0]; ty = y + next[k][1]; if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1) continue; if (a[tx][ty] == '.' && book[tx][ty] == 0) { book[tx][ty] = 1; dfs(tx, ty); //book[tx][ty] = 0; 因为是遍历图中的每一个点，与找到终点不一样，所以这个步骤删除 } } return; }

上述代码就是着色法的实现： 着色法：以某个点为源点对其临近的点进行着色

---

求一个图中有多少个独立子图 对图中每一个点进行一次DFS，并对其进行不同的着色

Floodfill漫水填充法 Floodfill算法在计算机图形学中有着非常广泛的应用。比如图像切割，物体识别 例如：Windows下画图软件的油漆桶就是基于这个算法

---

水管工游戏

输出通路，需要一个栈 每次进行尝试的时候入栈 如果尝试不成功，则将这个不成功的出栈

最后栈中保留的，就是正确的路线 当成功的时候，就输出栈中路线就可以了

这个我觉得收获最大是 形成路线 至于水管的选择还是dfs 不过，在选择水管的时候，可以选择进行多个dfs，给我带来了启发

#include<stdio.h> int a[51][51]; int book[51][51]; int n, m, flag = 0; struct note { int x; int y; }s[100]; //形成一个栈 int top = 0; void dfs(int x, int y, int front)//x,y代表位置,front代表进水口方向 { int i; //判断是否到达终点 //判断终点一定要在判断越界前面 if (x == n && y == m + 1) { flag = 1; for (i = 1; i <= top; i++) printf("(%d,%d)", s[i].x, s[i].y); return; } if (x < 1 || x>n || y<1 || y>m) { return; } if (book[x][y] == 1) //判断这个管道是不是已经使用过 return; book[x][y] = 1;//如果没有使用过，标记的当前管道 //将当前尝试入栈 top++; s[top].x = x; s[top].y = y; //枚举当前管道的每一种摆放方式。根据进水口的方向来决定管道方向 //当前管道是直道 if (a[x][y] >= 5 && a[x][y] <= 6) { //front代表进水口方向 if (front == 1) { dfs(x, y + 1, 1); } if (front == 2) { dfs(x + 1, y, 2); } if (front == 3) { dfs(x, y - 1, 3); } if (front == 4) { dfs(x - 1, y, 4); } } //当前是弯道的时候 //每个弯道有两种状态，因此对应于需要两个dfs if (a[x][y] >= 1 && a[x][y] <= 4) { if (front == 1) //如果进水口是左边 { dfs(x + 1, y, 2); //那么我下一个位置进水口只有上面和下面 dfs(x - 1, y, 4); } if (front == 2) { dfs(x, y + 1, 1); dfs(x, y - 1, 3); } if (front == 3) { dfs(x - 1, y, 4); dfs(x + 1, y, 2); } if (front == 4) { dfs(x, y + 1, 1); dfs(x, y - 1, 3); } } book[x][y] = 0; //取消标记 这是因为，这个尝试失败了，要换一种了 top--; //将当前尝试出栈 return; } int main() { int i, j, num = 0; scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } dfs(1, 1, 1); if (flag == 0) { printf("impossible\n"); } else printf("找到铺设方案\n"); }