专业实训记录2
深度优先搜索（回溯/洪水/剪枝）和广度优先搜索
具体的知识点内容在去年暑假的集训日常周记中已经有详细记录和分析，以下还是以题目的思路分析和代码记录为主。
深度优先搜索
问题A：全排列
题目描述：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入：
输出：由组成的所有不重复的数字序列，每行一个序列。每个数字占列。
Sample Input:
4
Sample Output:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
思路：全排列是回溯算法中比较经典的题目。
回溯算法从某种意义上来说也是一种穷举算法，穷举所有的可能性。
回溯算法的基本思想是逐步构建候选解，并在发现不能满足问题约束条件时进行回溯，重新尝试其他可能的选择。这个过程可以看作是在一棵决策树上的深度优先遍历。每一步的决策都会影响后续的决策路径，而回溯算法会在搜索的过程中不断地回退和前进，直到找到问题的解或者确定无解。
回溯算法的一般步骤如下：
- 选择： 从问题的可能解集中，选择一个候选解。
- 判定： 判断当前选择是否满足问题的条件。
- 如果满足条件，进入下一步。
- 如果不满足条件，回溯到上一步选择的状态，尝试其他的选择。
- 递归： 以递归的方式继续进行选择和判定，直到找到问题的解或者确定无解。
- 撤销： 如果在当前选择路径上找不到解，需要撤销上一步的选择，回到之前的状态，然后尝试其他的选择。
代码：
#include <iostream>
#include <cstdio>
using namespace std; // 用
const int M = 35;
int a[M], n; // n表示的是n个盒子n张牌,a-盒子
bool used[M]; // N张牌的状态，默认是没有用过在手中（false）
// 在第S个盒子放牌
void dfs(int s);
int main()
{
scanf("%d", &n);
dfs(1); // 输出全排列
return 0;
}
void dfs(int s)
{
//递归出口，走到第n+1个盒子，输出
if (s == n + 1)
{
for (int i = 1; i <= n; i++)
{
printf("%5d",a[i]);
}
printf("\n");
}
//枚举手中的牌1-n
for (int i = 1; i <= n; i++){
//第i张牌如果在手中，放在第s盒子里
if (!used[i])
{
a[s] = i;
used[i] = true;
dfs(s + 1); // 继续下一个盒子放
used[i] = false; // 回溯，取回牌
}
}
}
问题I：拆分自然数
题目描述：
任何一个大于1的自然数，总可以拆分成若干个小于的自然数之和。
当共种拆分方法：
输入：输入自然数
输出：输出拆分的方案
Sample Input:
7
Sample Output:
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
思路：
7=1+1+1+1+1+2 和 7=1+1+1+2+1+1 是同一种拆分情况，也就是说不同的拆分顺序视为同一种拆分情况。那怎么保证呢？只需要让下一个拆分出来的数大于等于前一个数即可
根据题目要求，拆分出来的数要小于n，因此类似于7=7这种情况是不满足条件的，不被视为一种拆分情况
递归函数的编写需要有两个参数，不妨假设第一个为s,第二个为t，s代表的含义为：待拆分的数据，t代表的含义为：t代表当前是第几个拆分出来的数据。此处一定要理解透彻这两个变量的含义。
对于参数s(请注意，s作为递归函数的参数，它的值是不断改变的)而言，它拆分出来的数据要小于等于s，并且当n==s时，即7=7,7不能作为7拆分出来的数据，这里的确比较难理解，不过之后你只需要根据代码去理解就可以了。
定义如下变量：int a[10001]={1}，a数组用来某个数拆分的各个数字，比如a[1]=1,a[2]=1,a[3]=1,a[4]=1,a[5]=1,a[6]=1,a[7]=1，就表示7被拆分为1+1+1+1+1+1+1。比如a[1]=1,a[2]=1,a[3]=2,a[4]=3，就表示7被拆分为1+1+2+3。
一定要注意，在尝试每一个数据时，一定要保证当前拆分出来的这个数据大于等于前面一个拆分出来的数据，不然会出现重复的情况，就像思路1中所提及的一样。
代码：
#include <iostream>
using namespace std;
int m;
int a[15] = {0};
// 深度优先搜索函数，n为当前剩余待拆分的值，s为当前存储位置
void dfs(int n, int s){
// 已经拆分完毕，输出满足条件的拆分组合
if(n==0){
if(s<=2) // 如果只有一个数或两个数，不满足要求，直接返回
return;
for(int i=1;i<s-1;i++){
cout << a[i] << "+";
}
cout << a[s-1] << endl;
return;
}
for(int i=1;i<=n;i++){
// 拆分的数必须大于等于上一个拆分的数，避免重复
if(i>= a[s-1]){
a[s] = i; // 将拆分的数 i 存入数组中的第 s 个位置
dfs(n-i,s+1); // 递归调用，继续拆分剩余部分
}
}
}
int main() {
cin >> m;
dfs(m,1);
return 0;
}
广度优先搜索
问题A：RED AND BLACK
题目描述：
一个矩形的房间铺着红色或者黑色的方砖。一个人站在红砖上不能移动，在黑砖上可以沿着上、下、左、右个方向移动到相邻的方砖。请编写一个程序，计算从起点出发可以到达的黑色方砖的数量（包括起点在内）
起点是@，要求：遍历所有黑砖
输入：
输入第一行是两个正整数和； 和分别表示方向和方向上的方砖数量。和都是正整数并且不超过.
接下来有行，每行包含个字符。每个字符表示方砖的颜色如下。
'.' - 黑砖
'＃' - 红砖
'@' - 起点
输出：输出从起点出发可以到达的黑砖的数量（包括起点在内）
Sample Input：
5 4
....#
.....
#@...
.#..#
Sample Output：
15
思路：
从起点 '@' 开始，沿着黑砖的方向逐步扩展，标记所有可以到达的黑砖，最后统计标记的数量即可。
以下是解决该问题的基本思路：
- 从输入中找到起点 '@' 的位置，作为起始点。
- 使用深度优先搜索，从起始点开始向上、下、左、右四个方向逐步扩展。对于每一个扩展出的位置，判断是否是黑砖（'.'），如果是黑砖则标记，并继续以该位置为新的起点进行深度优先搜索。
- 递归终止条件为越界或者当前位置是红砖（'＃'）。
- 统计所有被标记的黑砖的数量，即为起点出发可以到达的黑砖的数量。
代码：
#include <iostream>
#include <queue>
using namespace std;
int n, m, cnt; // n行, m列
char mp[25][25];
int dir[][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 搜索的方向向量
void dfs(int r, int c); // 从起点开始搜索，返回黑砖的数量
int main() {
int sr, sc;
while (cin >> m >> n && n != 0 && m != 0) {
// 输入地图信息
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mp[i][j];
if (mp[i][j] == '@') { //记录起点的位置
sr = i;
sc = j;
}
}
}
cnt = 0; // 每次处理一个数据集前，将cnt清零
dfs(sr, sc);
cout << cnt << endl;
}
return 0;
}
void dfs(int r, int c) {
cnt++;
// 起点入队并标记为红砖
mp[r][c] = '#';
for (int i = 0; i < 4; i++) {
int nr = r + dir[i][0]; // 新行
int nc = c + dir[i][1]; // 新列
if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && mp[nr][nc] == '.') {
dfs(nr, nc);
}
}
return;
}
问题D：马的移动
题目描述：
小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：给定两个棋盘上的方格和，马从跳到最少需要多少步？现请你编程解决这个问题。
提示
国际象棋棋盘为格*格，马的走子规则为，每步棋先横走或直走一格，然后再往外斜走一格
输入：
输入包含多组测试数据
每组输入由两个方格组成，每个方格包含一个小写字母，表示棋盘的列号，和一个整数，表示棋盘的行号
输出：
对于每组输入，输出一行“To get from xx to yy takes n knight moves.”
Sample Input：
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output：
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
思路：因为求最小移动步数，所以想到使用BFS来求，本题思路比较简单，只要按照题目意思去模拟马的移动就可以，套用模板公式。但需要注意的是，需要引入一个深度变量来计数(如果使用定义 struct pos )，同时因为多组测试数据输入，每次进行BFS搜索前需要进行一次 memset(mp,0,sizeof(mp))来重置棋盘上的标志信息。
代码：
//国际象棋棋盘上马的移动
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int dir[][2] = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}; // 马的八个移动方向
int mp[8][8];
int cnt;
int sx, sy, ex, ey;
int x, y;
void bfs(int r, int c);
int main() {
string s, e;
while (cin >> s >> e) {
memset(mp,0,sizeof(mp)); // 每组数据开始前，将棋盘清空
sx = s[0] - 'a', sy = s[1] - '1'; // 起点
ex = e[0] - 'a', ey = e[1] - '1'; // 终点
cnt = 0;
bfs(sx, sy);
cout << "To get from " << s << " to " << e << " takes " << cnt << " knight moves." << endl;
}
return 0;
}
void bfs(int r, int c) {
queue<pair<int, int>> q;
q.push(make_pair(r, c));
mp[r][c] = 1; // 标记已经走过
int step = 0;
while (!q.empty()) {
int size = q.size(); // 保存当前层的节点个数
while (size--) {
pair<int, int> p = q.front();
q.pop();
if (p.first == ex && p.second == ey) {
cnt = step;
return; // 找到终点，结束搜索
}
for (int i = 0; i < 8; i++) {
x = p.first + dir[i][0];
y = p.second + dir[i][1];
if (x >= 0 && x < 8 && y >= 0 && y < 8 && mp[x][y] == 0) {
q.push(make_pair(x, y));
mp[x][y] = 1;
}
}
}
step++; // 进入下一层
}
}