文章目录
- 前言
- 例14-1 四阶数独
- 前置知识：
- 例14-2八皇后
- 例14-3 kkksc03考前临时抱佛脚
- 例14-4 马的遍历
- 前置知识
- 例14-5 奇怪的电梯
- 例14-6 Meteor Shower S
- 习题14-1.1 选数
- 例14-1 四阶数独
- 前置知识：
- 例14-2八皇后
- 例14-3 kkksc03考前临时抱佛脚
- 例14-4 马的遍历
- 前置知识
- 例14-5 奇怪的电梯
- 例14-6 Meteor Shower S
- 习题14-1.1 选数
- 习题14-1.2 PERKET
- 习题14-2 迷宫
- 习题14-3 单词接龙
- 习题14-4 单词方阵
- 习题14-5 自然数的拆分问题
- 习题14-6 Lake Counting S
- 法一：DFS
- 法二：BFS
- 习题14-7 填充颜色
- 习题14-1.2 PERKET
- 习题14-2 迷宫
- 习题14-3 单词接龙
- 习题14-4 单词方阵
- 习题14-5 自然数的拆分问题
- 习题14-6 Lake Counting S
- 法一：DFS
- 法二：BFS
- 习题14-7 填充颜色
前言
本文详细讲解了dfs算法和bfs算法的原理以及模板实现，并且通过练习题展示了什么时候使用dfs，什么时候使用bfs
电子版教材链接：
我通过百度网盘分享的文件：深入浅出程序设计…pdf
链接：https://pan.baidu.com/s/1kmF8wZLnK3Zci7s1ffjRzw
提取码：Ra3Q
复制这段内容打开「百度网盘APP即可获取」
例14-1 四阶数独
前置知识：
dfs模板
void dfs(int k) k表示递归的层数,或者说要填第几个空
{if(所有空都填完了){判断最优解/记录答案return; }for(枚举这个空能填的选项)if(这个选项是合法的){记录下这个空dfs(k+1)取消这个空}
}
本题我们要填16个空，所以我们从第一个空开始填，并且往后填空进行搜索，搜到符合的就继续，不符合的就回溯进行下一个搜索
搜索的流程是，我们定义三个数组，每个数组的0和1状态表示这个数组是否被标记，如果符合：
每一行都填满1到4
每一列都填满1到4
每一个小方格(2x2)是否用过1到4的所有数
我们就填入数字，并且记录下来，去填下一个空
#include <bits/stdc++.h>
using namespace std;
int a[5*5],n = 4*4,ans = 0;
int b1[5][5],b2[5][5],b3[5][5];
void dfs(int x)
{if(x>n){ans++;for(int i = 1;i<=n;i++){printf("%d ",a[i]);if(i%4 == 0) puts("");}puts("");return;}int row = (x-1)/4 +1;int col = (x-1)%4 + 1;int block = (row-1) / 2 *2 + (col-1) /2 +1; // 标识当前格子属于哪一个 2×2 小宫格for(int i = 1;i<=4;i++){if(b1[row][i] == 0 && b2[col][i] == 0 && b3[block][i] == 0) // 最后一个是当前块 block没有使用过数字 i{a[x] = i;b1[row][i] = 1;b2[col][i] = 1;b3[block][i] = 1;dfs(x+1);b1[row][i] = 0;b2[col][i] = 0;b3[block][i] = 0;}}
}
int main()
{dfs(1);printf("%d",ans);return 0;
}
例14-2八皇后
#include <bits/stdc++.h>
using namespace std;
#define maxn 100
int a[maxn],n,ans = 0;
int b1[maxn],b2[maxn],b3[maxn]; // b1表示列，b2表示右下行斜线，b3表示左上行斜线
void dfs(int x)
{if(x>n){ans++;if(ans<=3){for(int i = 1;i<=n;i++)printf(“%d ”,a[i]);puts(“”);}return;}for(int i=1;i<=n;i++)if(b1[i] == 0 && b2[x+i] ==0 && b3[x-i+15] == 0){ // 由于n<13所以我们这里为了防止x-y小于0，所以我们就扩充为列x-i+15，本质上其实表示的还是x-ya[x] = i;b1[i] = 1;b2[x+i] = 1;b3[x-i+15] = 1;dfs(x+1);b1[i] = 0;b2[x+i] = 0;b3[x-i+15] = 0;}
}int main()
{scanf(“%d”,&n);dfs(1);printf(“%d”,ans);return 0;
}
例14-3 kkksc03考前临时抱佛脚
每次我们都只需要考虑一科的时间，所以我们要尽量的用完大脑可以左右互用这个性质，把所有的题分为两组，使得左脑做一组，右脑做一组，然后意思就是使得分得的两组分别的耗时总和最为接近(避免有一边大脑是闲置的造成时间的浪费)
再优化一下上面的分析，就是在这些题目中找寻一个子集，使得子集耗时不超过总耗时的一半，说到子集，我们当然可以考虑使用位运算进行枚举，但是最后的结果是2的20次幂，显然是百万级别的，进行了很多不必要的计算，所以我们考虑使用深度优先搜索的方法，搜索是否把题目归入子集，如果是就继续搜索，不是就回溯
#include <bits/stdc++.h>
using namespace std;
int nowtime,maxtime,sum;
int ans,maxdeep;
int s[4],a[21];
void dfs(int x)
{if(x>maxdeep){maxtime = max(maxtime,nowtime);return;}if(nowtime +a[x] <= sum /2){nowtime += a[x];dfs(x+1);nowtime -= a[x]; }dfs(x+1);
}int main()
{cin >> s[0] >> s[1] >> s[2] >> s[3];for(int i = 0;i<4;i++){nowtime = 0;maxdeep = s[i];sum = 0;for(int j = 1;j<=s[i];j++){cin >> a[j];sum += a[j];}maxtime = 0;dfs(1);ans += (sum-maxtime);}cout << ans;return 0;
}
例14-4 马的遍历
前置知识
队列实现广度优先搜索(bfs)
Q.push(初始状态); // 将初始状态入队
while(!Q.empty()){State u = Q.front(); // 取出队首Q.pop(); // 出队for(枚举所有可扩展状态)if(是合法的)Q.push(v); //入队
}
广度优先搜索用于解决连通性和最短路等问题，分析每种状态和初始状态的距离，与初始状态越接近的情况就会越优先进行考虑，每个时刻要做的事情就是从上个时刻(阶段)每个状态扩展出新的状态
本题先建立一个结构体数组用于存储扩展的结点，先让起点入队，然后在队列取状态逐个扩展，又因为每个点只被扩展了一次，所以复杂度是O(mn)级别的
#include <bits/stdc++.>
using namespace std;
#define maxn 310
struct coord{int x,y;
};
queue<coord> Q;
int ans[maxn][maxn];
int walk[8][2] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};int main()
{int n,m,sx,sy;memset(ans,-1,sizeof(ans));cin >> n >> m >> sx >> sy;coord temp = {sx,sy};Q.push(tmp); // 使起点入队扩展ans[sx][sy] = 0;while(!Q.empty()){coord u = Q.front();int ux = u.x,uy = u.y;Q.pop();for(int k = 0;k<8;k++){int x = ux+walk[k][0] ,y = uy+walk[k][1];int d = ans[ux][uy]; // 记录当前的点作为初始点if(x<1 || x>n || y<1 || y>m || ans[x][y] != -1){continue;}ans[x][y] = d+1; // 每次跳一步，距离就是上一层距离 +1coord tmp = {x,y};Q.push(tmp);}}for(int i = 1;i<=n;i++,puts(""))for(int j = 1;j<=m;j++)printf("%d ",ans[i][j]); return 0;
}
例14-5 奇怪的电梯
从起点开始，往上或者往下进行扩展，可以到达”按1次按钮的地方“，这些”按1次按钮的地方“再分别往上或者往下进行扩展(前提是在大厦范围内，且没有访问过)，就可以到达”按2次按钮的地方“
#include <bits/stdc++.h>
using namespace std;struct node{int floor,d;
};
queue<node> Q;
int n,a,b;
int k[1000],vis[1000];
int main()
{cin >> n >> a >> b;for(int i = 1;i<=n;i++)cin >> k[i];Q.push((node){a,0}); // 入队初始节点vis[a] = 1; node now;while(!Q.empty()){now = Q.front();Q.pop();if(now.floor == b) break;for(inb sign = -1;sign<=1;sign +=2){ // 用于表示状态-1和1int dist = now.floor + k[now.floor] * sign;if(dist>=1 && dist<=n && vis[dist] == 0){Q.push((node){dist,now.d+1});vis[dist] = 1;}}}if(now.floor == b)cout << now.d << endl;else cout << -1 << endl;return 0;
}
例14-6 Meteor Shower S
本题由于多出了时间的限制，我们需要单独开一个数组记录一下陨石砸到的时间和位置，如果贝西在这个时间之前通过这个位置，就是合法的，反之就非法的；如果贝西跑到了300x300之外的地方，那么久绝对是安全的，输出最短到这个位置的距离即可
#include <bits/stdc++.h>
using namespace std;#define maxn 310struct nihao {int x, y;
};queue<nihao> Q;
int ans[maxn][maxn], death[maxn][maxn];
int w[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}}; // 右、下、左、上int main() {int m, Ans = 1e9;memset(ans, -1, sizeof(ans));memset(death, 0x7f, sizeof(death)); cin >> m;for (int i = 1; i <= m; i++) {int x, y, t;cin >> x >> y >> t;if (x >= 0 && y >= 0 && x < maxn && y < maxn)death[x][y] = min(death[x][y], t);for (int k = 0; k < 4; k++) {int nx = x + w[k][0], ny = y + w[k][1];if (nx >= 0 && ny >= 0 && nx < maxn && ny < maxn)death[nx][ny] = min(death[nx][ny], t);}}if (death[0][0] == 0) {cout << -1 << endl;return 0;}Q.push({0, 0});ans[0][0] = 0;while (!Q.empty()) {nihao u = Q.front(); Q.pop();int ux = u.x, uy = u.y;for (int k = 0; k < 4; k++) {int x = ux + w[k][0], y = uy + w[k][1];if (x < 0 || y < 0 || x >= maxn || y >= maxn) continue;if (ans[x][y] != -1) continue;if (ans[ux][uy] + 1 >= death[x][y]) continue;ans[x][y] = ans[ux][uy] + 1;Q.push({x, y});}}for (int i = 0; i < maxn; i++) {for (int j = 0; j < maxn; j++) {if (death[i][j] > 1000 && ans[i][j] != -1)Ans = min(Ans, ans[i][j]);}}if (Ans == 1e9)cout << -1 << endl;elsecout << Ans << endl;return 0;
}
习题14-1.1 选数
对于这道题，我们之前在暴力枚举章节中使用了位运算的方法来选取长度为k的子集再实现质数的判断，现在我们也可以直接使用深搜去搜索满足要求的点并且输出
我们使用了一种隐式回溯的方法避免了定义标记数组，不会造成状态污染
电子版教材链接：
我通过百度网盘分享的文件：深入浅出程序设计…pdf
链接：https://pan.baidu.com/s/1kmF8wZLnK3Zci7s1ffjRzw
提取码：Ra3Q
复制这段内容打开「百度网盘APP即可获取」
例14-1 四阶数独
前置知识：
dfs模板
void dfs(int k) k表示递归的层数,或者说要填第几个空
{if(所有空都填完了){判断最优解/记录答案return; }for(枚举这个空能填的选项)if(这个选项是合法的){记录下这个空dfs(k+1)取消这个空}
}
本题我们要填16个空，所以我们从第一个空开始填，并且往后填空进行搜索，搜到符合的就继续，不符合的就回溯进行下一个搜索
搜索的流程是，我们定义三个数组，每个数组的0和1状态表示这个数组是否被标记，如果符合：
每一行都填满1到4
每一列都填满1到4
每一个小方格(2x2)是否用过1到4的所有数
我们就填入数字，并且记录下来，去填下一个空
#include <bits/stdc++.h>
using namespace std;
int a[5*5],n = 4*4,ans = 0;
int b1[5][5],b2[5][5],b3[5][5];
void dfs(int x)
{if(x>n){ans++;for(int i = 1;i<=n;i++){printf("%d ",a[i]);if(i%4 == 0) puts("");}puts("");return;}int row = (x-1)/4 +1;int col = (x-1)%4 + 1;int block = (row-1) / 2 *2 + (col-1) /2 +1; // 标识当前格子属于哪一个 2×2 小宫格for(int i = 1;i<=4;i++){if(b1[row][i] == 0 && b2[col][i] == 0 && b3[block][i] == 0) // 最后一个是当前块 block没有使用过数字 i{a[x] = i;b1[row][i] = 1;b2[col][i] = 1;b3[block][i] = 1;dfs(x+1);b1[row][i] = 0;b2[col][i] = 0;b3[block][i] = 0;}}
}
int main()
{dfs(1);printf("%d",ans);return 0;
}
例14-2八皇后
#include <bits/stdc++.h>
using namespace std;
#define maxn 100
int a[maxn],n,ans = 0;
int b1[maxn],b2[maxn],b3[maxn]; // b1表示列，b2表示右下行斜线，b3表示左上行斜线
void dfs(int x)
{if(x>n){ans++;if(ans<=3){for(int i = 1;i<=n;i++)printf(“%d ”,a[i]);puts(“”);}return;}for(int i=1;i<=n;i++)if(b1[i] == 0 && b2[x+i] ==0 && b3[x-i+15] == 0){ // 由于n<13所以我们这里为了防止x-y小于0，所以我们就扩充为列x-i+15，本质上其实表示的还是x-ya[x] = i;b1[i] = 1;b2[x+i] = 1;b3[x-i+15] = 1;dfs(x+1);b1[i] = 0;b2[x+i] = 0;b3[x-i+15] = 0;}
}int main()
{scanf(“%d”,&n);dfs(1);printf(“%d”,ans);return 0;
}
例14-3 kkksc03考前临时抱佛脚
每次我们都只需要考虑一科的时间，所以我们要尽量的用完大脑可以左右互用这个性质，把所有的题分为两组，使得左脑做一组，右脑做一组，然后意思就是使得分得的两组分别的耗时总和最为接近(避免有一边大脑是闲置的造成时间的浪费)
再优化一下上面的分析，就是在这些题目中找寻一个子集，使得子集耗时不超过总耗时的一半，说到子集，我们当然可以考虑使用位运算进行枚举，但是最后的结果是2的20次幂，显然是百万级别的，进行了很多不必要的计算，所以我们考虑使用深度优先搜索的方法，搜索是否把题目归入子集，如果是就继续搜索，不是就回溯
#include <bits/stdc++.h>
using namespace std;
int nowtime,maxtime,sum;
int ans,maxdeep;
int s[4],a[21];
void dfs(int x)
{if(x>maxdeep){maxtime = max(maxtime,nowtime);return;}if(nowtime +a[x] <= sum /2){nowtime += a[x];dfs(x+1);nowtime -= a[x]; }dfs(x+1);
}int main()
{cin >> s[0] >> s[1] >> s[2] >> s[3];for(int i = 0;i<4;i++){nowtime = 0;maxdeep = s[i];sum = 0;for(int j = 1;j<=s[i];j++){cin >> a[j];sum += a[j];}maxtime = 0;dfs(1);ans += (sum-maxtime);}cout << ans;return 0;
}
例14-4 马的遍历
前置知识
队列实现广度优先搜索(bfs)
Q.push(初始状态); // 将初始状态入队
while(!Q.empty()){State u = Q.front(); // 取出队首Q.pop(); // 出队for(枚举所有可扩展状态)if(是合法的)Q.push(v); //入队
}
广度优先搜索用于解决连通性和最短路等问题，分析每种状态和初始状态的距离，与初始状态越接近的情况就会越优先进行考虑，每个时刻要做的事情就是从上个时刻(阶段)每个状态扩展出新的状态
本题先建立一个结构体数组用于存储扩展的结点，先让起点入队，然后在队列取状态逐个扩展，又因为每个点只被扩展了一次，所以复杂度是O(mn)级别的
#include <bits/stdc++.>
using namespace std;
#define maxn 310
struct coord{int x,y;
};
queue<coord> Q;
int ans[maxn][maxn];
int walk[8][2] = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};int main()
{int n,m,sx,sy;memset(ans,-1,sizeof(ans));cin >> n >> m >> sx >> sy;coord temp = {sx,sy};Q.push(tmp); // 使起点入队扩展ans[sx][sy] = 0;while(!Q.empty()){coord u = Q.front();int ux = u.x,uy = u.y;Q.pop();for(int k = 0;k<8;k++){int x = ux+walk[k][0] ,y = uy+walk[k][1];int d = ans[ux][uy]; // 记录当前的点作为初始点if(x<1 || x>n || y<1 || y>m || ans[x][y] != -1){continue;}ans[x][y] = d+1; // 每次跳一步，距离就是上一层距离 +1coord tmp = {x,y};Q.push(tmp);}}for(int i = 1;i<=n;i++,puts(""))for(int j = 1;j<=m;j++)printf("%d ",ans[i][j]); return 0;
}
例14-5 奇怪的电梯
从起点开始，往上或者往下进行扩展，可以到达”按1次按钮的地方“，这些”按1次按钮的地方“再分别往上或者往下进行扩展(前提是在大厦范围内，且没有访问过)，就可以到达”按2次按钮的地方“
#include <bits/stdc++.h>
using namespace std;struct node{int floor,d;
};
queue<node> Q;
int n,a,b;
int k[1000],vis[1000];
int main()
{cin >> n >> a >> b;for(int i = 1;i<=n;i++)cin >> k[i];Q.push((node){a,0}); // 入队初始节点vis[a] = 1; node now;while(!Q.empty()){now = Q.front();Q.pop();if(now.floor == b) break;for(inb sign = -1;sign<=1;sign +=2){ // 用于表示状态-1和1int dist = now.floor + k[now.floor] * sign;if(dist>=1 && dist<=n && vis[dist] == 0){Q.push((node){dist,now.d+1});vis[dist] = 1;}}}if(now.floor == b)cout << now.d << endl;else cout << -1 << endl;return 0;
}
例14-6 Meteor Shower S
本题由于多出了时间的限制，我们需要单独开一个数组记录一下陨石砸到的时间和位置，如果贝西在这个时间之前通过这个位置，就是合法的，反之就非法的；如果贝西跑到了300x300之外的地方，那么久绝对是安全的，输出最短到这个位置的距离即可
#include <bits/stdc++.h>
using namespace std;#define maxn 310struct nihao {int x, y;
};queue<nihao> Q;
int ans[maxn][maxn], death[maxn][maxn];
int w[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}}; // 右、下、左、上int main() {int m, Ans = 1e9;memset(ans, -1, sizeof(ans));memset(death, 0x7f, sizeof(death)); cin >> m;for (int i = 1; i <= m; i++) {int x, y, t;cin >> x >> y >> t;if (x >= 0 && y >= 0 && x < maxn && y < maxn)death[x][y] = min(death[x][y], t);for (int k = 0; k < 4; k++) {int nx = x + w[k][0], ny = y + w[k][1];if (nx >= 0 && ny >= 0 && nx < maxn && ny < maxn)death[nx][ny] = min(death[nx][ny], t);}}if (death[0][0] == 0) {cout << -1 << endl;return 0;}Q.push({0, 0});ans[0][0] = 0;while (!Q.empty()) {nihao u = Q.front(); Q.pop();int ux = u.x, uy = u.y;for (int k = 0; k < 4; k++) {int x = ux + w[k][0], y = uy + w[k][1];if (x < 0 || y < 0 || x >= maxn || y >= maxn) continue;if (ans[x][y] != -1) continue;if (ans[ux][uy] + 1 >= death[x][y]) continue;ans[x][y] = ans[ux][uy] + 1;Q.push({x, y});}}for (int i = 0; i < maxn; i++) {for (int j = 0; j < maxn; j++) {if (death[i][j] > 1000 && ans[i][j] != -1)Ans = min(Ans, ans[i][j]);}}if (Ans == 1e9)cout << -1 << endl;elsecout << Ans << endl;return 0;
}
习题14-1.1 选数
对于这道题，我们之前在暴力枚举章节中使用了位运算的方法来选取长度为k的子集再实现质数的判断，现在我们也可以直接使用深搜去搜索满足要求的点并且输出
我们使用了一种隐式回溯的方法避免了定义标记数组，不会造成状态污染
完整实现代码如下：
#include <bits/stdc++.h>
using namespace std;
int n,k,a[25];
long long ans;bool isPrime(int x)
{if(x == 1) return 0;for(int i = 2;i<=sqrt(x);i++){if(x%i == 0) return 0;}return 1;}// 隐式回溯写法
void dfs1(int m,int sum,int startx) // 其中m表示选择几个数，sum表示此时的和，startx表示从哪个索引开始
{if(m == k){if(isPrime(sum)){ans ++;}return ;}for(int i = startx;i<n;i++) // 隐式的点在于每次都会更新startx，每次搜索的起点都是不一样的{dfs1(m+1,sum+a[i],i+1);}}// 显式回溯写法
int v[30];
void dfs2(int m, int sum) {if (m == k) {if (isPrime(sum)) ans++;return;}for (int i = 0; i < n; i++) {if (!vis[i]) {// 选择 a[i]vis[i] = true;dfs2(m + 1, sum + a[i]);// 撤销选择 a[i]vis[i] = false;}}int main()
{cin >> n >> k;for(int i = 0;i<n;i++)cin >> a[i];dfs1(0,0,0);cout << ans << endl;return 0;
}
习题14-1.2 PERKET
本题要找到总酸度和总苦度的最小绝对差，所以我们可以进行深搜来得到答案
#include <bits/stdc++.h>
using namespace std;
int N,s[12],b[12],mi=2000000001;void dfs(int x,int S,int B)
{if(x == N){mi = min(mi,abs(S-B));return ;}dfs(x+1,S*s[x],B+b[x]); // 搜索添加的dfs(x+1,S,B); // 搜索不添加的
}void dfs(int x) { for(int i=1;i<=n;i++) { if(f[i]==0) //没有查找过的才操作 { c*=s[i]; y+=b[i]; ans=min(ans,abs(c-y)); //取最小值 f[i]=1; //记录 dfs(x+1); f[i]=0; //取消记录 c/=s[i]; y-=b[i]; } }
}int main()
{scanf("%d",&N);for(int i=0;i<N;i++)scanf("%d %d",&s[i],&b[i]);if(N==1){printf("%d",abs(s[0]-b[0]));return 0;}dfs(0,1,0); // 这里要注意S必须为1，如果是0后续乘积就都是0了printf("%d",mi);return 0;
}
习题14-2 迷宫
#include <bits/stdc++.h>
using namespace std;int n, m, t, sx, sy, fx, fy, b, c, a[10][10], ans;
bool temp[10][10];
int w[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}}; // 右、下、左、上void dfs(int x, int y) {if (x == fx && y == fy) {ans++;return;}for (int i = 0; i < 4; i++) {int nx = x + w[i][0];int ny = y + w[i][1];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&!temp[nx][ny] && a[nx][ny] == -1) {temp[nx][ny] = 1;dfs(nx, ny);temp[nx][ny] = 0; }}
}int main() {memset(a, -1, sizeof(a));cin >> n >> m >> t;cin >> sx >> sy >> fx >> fy;for (int i = 1; i <= t; i++) {cin >> b >> c;a[b][c] = 0; }temp[sx][sy] = 1; dfs(sx, sy);cout << ans << endl;return 0;
}
习题14-3 单词接龙
枚举每一个有用的单词，然后判断单词的开头和上个单词的结尾相同，如果相同就继续枚举，没有就回溯
#include <bits/stdc++.h>
using namespace std;const int N = 66;
int n, ts = 0, ans = 0;
int v[N]; // 限制字符串的使用次数
string s[N];// 计算 s1 后缀与 s2 前缀的最大重叠长度
int max_overlong(const string& s1, const string& s2) {int len1 = s1.size(), len2 = s2.size();int max_overlap = 0;int max_len = min(len1, len2);for (int i = 1; i <= max_len; i++) {if (s1.substr(len1 - i, i) == s2.substr(0, i)) {max_overlap = i;}}return max_overlap;
}// 深度优先搜索
void dfs(const string& cur) {ans = max(ans, ts);for (int i = 0; i < n; i++) {if (v[i] < 2) {int overlap = get_overlap(cur, s[i]);if (overlap < s[i].size()) { // 有意义的拼接v[i]++;ts += s[i].size() - overlap;dfs(cur + s[i].substr(overlap));ts -= s[i].size() - overlap;v[i]--;}}}
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> s[i];char c;cin >> c;for (int i = 0; i < n; i++) {if (s[i][0] == c) {ts = s[i].size();v[i]++;dfs(s[i]);v[i]--;}}cout << ans << endl;return 0;
}
习题14-4 单词方阵
本题就是要寻找，在给定的单词方阵中，是否有横竖撇那八列存在单词yizhong的完整拼写，其它的字母全部变成*，为了找到目标，我们使用深度优先搜索算法
首先要先确定第一个字母是y，在此基础上我们去查找后面的六个字母
查找六个字母的代码为：
其中i表示是8个方向中的哪个方向
for(int j = 1;j <= 6;j++) {
//以1个方向比较 “izhong” int nx = x + j*dx[i]; int ny = y + j*dy[i]; if(nx < 1 || nx > n || ny < 1 || ny > n) { //判越界 flag = 0; break; } if(cmp[j] != A[nx][ny]){ flag = 0; break; }
}
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int dx[] = {1, 1, 1, 0, 0, -1,-1,-1 }; //方向数组
const int dy[] = {1, 0,-1, 1,-1, 0 , 1,-1 };
const string cmp = "yizhong"; char A[maxn][maxn],ans[maxn][maxn];
int mark[maxn][maxn],n;void dfs(int x,int y)
{for(int i = 0;i<8;i++){int flag = 1;for(int j = 0;j<6;j++){int nx = x+j*dx[i];int ny = y+j*dy[i];if(nx<1 || nx>n || ny<1 || ny >n){flag = 0;break;}if(cmp[j]!=A[nx][ny]){flag = 0;break;}}if(flag = 0) continue;for(int j = 0;j <= 6;j++) { //符合就记录在ans数组里 int nx = x + j*dx[i]; int ny = y + j*dy[i]; ans[nx][ny] = A[nx][ny]; }}
}int main()
{cin >> n; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { cin >> A[i][j]; } } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(A[i][j] == 'y') dfs(i,j);//如果发现有y就开始搜索 }}for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++){if(ans[i][j] == 0) ans[i][j] = '*';//如果没有改动就输出* cout << ans[i][j]; }cout << endl; }return 0;
}
习题14-5 自然数的拆分问题
#include <bits/stdc++.h>
using namespace std;int a[11] = {1}, n;void print(int t) {for (int i = 1; i < t; i++)cout << a[i] << "+";cout << a[t] << endl;
}void dfs(int s, int t) {for (int i = a[t - 1]; i <= s; i++) {a[t] = i;s -= i;if (s == 0 && i != n) print(t);elsedfs(s, t + 1);s += i; }
}int main() {cin >> n;dfs(n, 1);return 0;
}
习题14-6 Lake Counting S
本题给了一个图，需要我们在图内找到闭合的水潭，并且统计水潭的数量，这题我们可以使用搜索来进行解决
法一：DFS
#include <bits/stdc++.h>
using namespace std;
char a[101][101];
int ans;
int n,m;void dfs(int x,int y)
{a[x][y] = '.'; int dx,dy;for(int i = -1;i<=1;i++){for(int j = -1;j<=1;j++){dx=x+i;dy=y+j;if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'){dfs(dx,dy);}}}
}int main()
{scanf("%d %d", &n, &m);for(int i = 0; i < n; i++)scanf("%s", a[i]);for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(a[i][j] == 'W') {dfs(i, j);ans++;}}}printf("%d\n", ans);return 0;
}
法二：BFS
#include <bits/stdc++.h>
using namespace std;
queue<int>h;//行的队列
queue<int>p;//列的队列
int n,m;
int ans;
char s[101][101];void bfs(int x,int y){s[x][y]='.';int dx,dy;for(int i=-1;i<=1;i++){for(int j=-1;j<=1;j++){dx=x+i;dy=y+j;if(dx>=0&&dx<n&&dy>=0&&dy<m&&s[dx][dy]=='W'){h.push(dx);p.push(dy);}}}
}
int main(){cin >> n >> m;for(int i=0;i<n;i++){scanf("%s",s[i]);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='W'){h.push(i);p.push(j);while(!h.empty()){ //如果队列不为空bfs(h.front(),p.front()); //广搜队列前面的元素h.pop();p.pop(); //弹出元素}ans++;}}}printf("%d",ans);return 0;
}
习题14-7 填充颜色
我们首先要找到1的闭合圈，其次把闭合圈内全部换为2，但是边界仍然是1，所以我们正常输入，在外面围一圈0，再从周围搜索就行了
#include<bits/stdc++.h>
using namespace std;
int n,a[35][35];queue<pair<int,int> >que;
void bfs(int x, int y)
{int dx[5] = { 0,-1,0,1,0 }, dy[5] = { 0,0,1,0,-1 };que.push(pair<int, int>(x, y));while (!que.empty()){pair<int, int>t = que.front();que.pop();a[t.first][t.second] = 2;for (int i = 1; i <= 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 0 && nx <= n+1 && ny >= 0 && ny <= n+1 && a[nx][ny] == 0) {que.push({nx,ny});}}}
}int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];bfs(0,0);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<2-a[i][j]<<' ';cout<<endl;}return 0;
}
完整实现代码如下：
#include <bits/stdc++.h>
using namespace std;
int n,k,a[25];
long long ans;bool isPrime(int x)
{if(x == 1) return 0;for(int i = 2;i<=sqrt(x);i++){if(x%i == 0) return 0;}return 1;}// 隐式回溯写法
void dfs1(int m,int sum,int startx) // 其中m表示选择几个数，sum表示此时的和，startx表示从哪个索引开始
{if(m == k){if(isPrime(sum)){ans ++;}return ;}for(int i = startx;i<n;i++) // 隐式的点在于每次都会更新startx，每次搜索的起点都是不一样的{dfs1(m+1,sum+a[i],i+1);}}// 显式回溯写法
int v[30];
void dfs2(int m, int sum) {if (m == k) {if (isPrime(sum)) ans++;return;}for (int i = 0; i < n; i++) {if (!vis[i]) {// 选择 a[i]vis[i] = true;dfs2(m + 1, sum + a[i]);// 撤销选择 a[i]vis[i] = false;}}int main()
{cin >> n >> k;for(int i = 0;i<n;i++)cin >> a[i];dfs1(0,0,0);cout << ans << endl;return 0;
}
习题14-1.2 PERKET
本题要找到总酸度和总苦度的最小绝对差，所以我们可以进行深搜来得到答案
#include <bits/stdc++.h>
using namespace std;
int N,s[12],b[12],mi=2000000001;void dfs(int x,int S,int B)
{if(x == N){mi = min(mi,abs(S-B));return ;}dfs(x+1,S*s[x],B+b[x]); // 搜索添加的dfs(x+1,S,B); // 搜索不添加的
}void dfs(int x) { for(int i=1;i<=n;i++) { if(f[i]==0) //没有查找过的才操作 { c*=s[i]; y+=b[i]; ans=min(ans,abs(c-y)); //取最小值 f[i]=1; //记录 dfs(x+1); f[i]=0; //取消记录 c/=s[i]; y-=b[i]; } }
}int main()
{scanf("%d",&N);for(int i=0;i<N;i++)scanf("%d %d",&s[i],&b[i]);if(N==1){printf("%d",abs(s[0]-b[0]));return 0;}dfs(0,1,0); // 这里要注意S必须为1，如果是0后续乘积就都是0了printf("%d",mi);return 0;
}
习题14-2 迷宫
#include <bits/stdc++.h>
using namespace std;int n, m, t, sx, sy, fx, fy, b, c, a[10][10], ans;
bool temp[10][10];
int w[4][2] = {{0,1}, {1,0}, {-1,0}, {0,-1}}; // 右、下、左、上void dfs(int x, int y) {if (x == fx && y == fy) {ans++;return;}for (int i = 0; i < 4; i++) {int nx = x + w[i][0];int ny = y + w[i][1];if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&!temp[nx][ny] && a[nx][ny] == -1) {temp[nx][ny] = 1;dfs(nx, ny);temp[nx][ny] = 0; }}
}int main() {memset(a, -1, sizeof(a));cin >> n >> m >> t;cin >> sx >> sy >> fx >> fy;for (int i = 1; i <= t; i++) {cin >> b >> c;a[b][c] = 0; }temp[sx][sy] = 1; dfs(sx, sy);cout << ans << endl;return 0;
}
习题14-3 单词接龙
枚举每一个有用的单词，然后判断单词的开头和上个单词的结尾相同，如果相同就继续枚举，没有就回溯
#include <bits/stdc++.h>
using namespace std;const int N = 66;
int n, ts = 0, ans = 0;
int v[N]; // 限制字符串的使用次数
string s[N];// 计算 s1 后缀与 s2 前缀的最大重叠长度
int max_overlong(const string& s1, const string& s2) {int len1 = s1.size(), len2 = s2.size();int max_overlap = 0;int max_len = min(len1, len2);for (int i = 1; i <= max_len; i++) {if (s1.substr(len1 - i, i) == s2.substr(0, i)) {max_overlap = i;}}return max_overlap;
}// 深度优先搜索
void dfs(const string& cur) {ans = max(ans, ts);for (int i = 0; i < n; i++) {if (v[i] < 2) {int overlap = get_overlap(cur, s[i]);if (overlap < s[i].size()) { // 有意义的拼接v[i]++;ts += s[i].size() - overlap;dfs(cur + s[i].substr(overlap));ts -= s[i].size() - overlap;v[i]--;}}}
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> s[i];char c;cin >> c;for (int i = 0; i < n; i++) {if (s[i][0] == c) {ts = s[i].size();v[i]++;dfs(s[i]);v[i]--;}}cout << ans << endl;return 0;
}
习题14-4 单词方阵
本题就是要寻找，在给定的单词方阵中，是否有横竖撇那八列存在单词yizhong的完整拼写，其它的字母全部变成*，为了找到目标，我们使用深度优先搜索算法
首先要先确定第一个字母是y，在此基础上我们去查找后面的六个字母
查找六个字母的代码为：
其中i表示是8个方向中的哪个方向
for(int j = 1;j <= 6;j++) {
//以1个方向比较 “izhong” int nx = x + j*dx[i]; int ny = y + j*dy[i]; if(nx < 1 || nx > n || ny < 1 || ny > n) { //判越界 flag = 0; break; } if(cmp[j] != A[nx][ny]){ flag = 0; break; }
}
完整代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int dx[] = {1, 1, 1, 0, 0, -1,-1,-1 }; //方向数组
const int dy[] = {1, 0,-1, 1,-1, 0 , 1,-1 };
const string cmp = "yizhong"; char A[maxn][maxn],ans[maxn][maxn];
int mark[maxn][maxn],n;void dfs(int x,int y)
{for(int i = 0;i<8;i++){int flag = 1;for(int j = 0;j<6;j++){int nx = x+j*dx[i];int ny = y+j*dy[i];if(nx<1 || nx>n || ny<1 || ny >n){flag = 0;break;}if(cmp[j]!=A[nx][ny]){flag = 0;break;}}if(flag = 0) continue;for(int j = 0;j <= 6;j++) { //符合就记录在ans数组里 int nx = x + j*dx[i]; int ny = y + j*dy[i]; ans[nx][ny] = A[nx][ny]; }}
}int main()
{cin >> n; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { cin >> A[i][j]; } } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(A[i][j] == 'y') dfs(i,j);//如果发现有y就开始搜索 }}for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++){if(ans[i][j] == 0) ans[i][j] = '*';//如果没有改动就输出* cout << ans[i][j]; }cout << endl; }return 0;
}
习题14-5 自然数的拆分问题
#include <bits/stdc++.h>
using namespace std;int a[11] = {1}, n;void print(int t) {for (int i = 1; i < t; i++)cout << a[i] << "+";cout << a[t] << endl;
}void dfs(int s, int t) {for (int i = a[t - 1]; i <= s; i++) {a[t] = i;s -= i;if (s == 0 && i != n) print(t);elsedfs(s, t + 1);s += i; }
}int main() {cin >> n;dfs(n, 1);return 0;
}
习题14-6 Lake Counting S
本题给了一个图，需要我们在图内找到闭合的水潭，并且统计水潭的数量，这题我们可以使用搜索来进行解决
法一：DFS
#include <bits/stdc++.h>
using namespace std;
char a[101][101];
int ans;
int n,m;void dfs(int x,int y)
{a[x][y] = '.'; int dx,dy;for(int i = -1;i<=1;i++){for(int j = -1;j<=1;j++){dx=x+i;dy=y+j;if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W'){dfs(dx,dy);}}}
}int main()
{scanf("%d %d", &n, &m);for(int i = 0; i < n; i++)scanf("%s", a[i]);for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(a[i][j] == 'W') {dfs(i, j);ans++;}}}printf("%d\n", ans);return 0;
}
法二：BFS
#include <bits/stdc++.h>
using namespace std;
queue<int>h;//行的队列
queue<int>p;//列的队列
int n,m;
int ans;
char s[101][101];void bfs(int x,int y){s[x][y]='.';int dx,dy;for(int i=-1;i<=1;i++){for(int j=-1;j<=1;j++){dx=x+i;dy=y+j;if(dx>=0&&dx<n&&dy>=0&&dy<m&&s[dx][dy]=='W'){h.push(dx);p.push(dy);}}}
}
int main(){cin >> n >> m;for(int i=0;i<n;i++){scanf("%s",s[i]);}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='W'){h.push(i);p.push(j);while(!h.empty()){ //如果队列不为空bfs(h.front(),p.front()); //广搜队列前面的元素h.pop();p.pop(); //弹出元素}ans++;}}}printf("%d",ans);return 0;
}
习题14-7 填充颜色
我们首先要找到1的闭合圈，其次把闭合圈内全部换为2，但是边界仍然是1，所以我们正常输入，在外面围一圈0，再从周围搜索就行了
#include<bits/stdc++.h>
using namespace std;
int n,a[35][35];queue<pair<int,int> >que;
void bfs(int x, int y)
{int dx[5] = { 0,-1,0,1,0 }, dy[5] = { 0,0,1,0,-1 };que.push(pair<int, int>(x, y));while (!que.empty()){pair<int, int>t = que.front();que.pop();a[t.first][t.second] = 2;for (int i = 1; i <= 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 0 && nx <= n+1 && ny >= 0 && ny <= n+1 && a[nx][ny] == 0) {que.push({nx,ny});}}}
}int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];bfs(0,0);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<2-a[i][j]<<' ';cout<<endl;}return 0;
}
