【算法设计-搜索】回溯法应用举例（1）

0. 回溯模板

搜索算法中的回溯策略，也是深度优先搜索的一种策略，比较接近早期的人工智能。毕竟，搜索是人工智能技术中进行问题求解的基本技术，很多问题都可以归结到某种搜索。

下面给出回溯算法的模板，很多题目其实可以套用该模板快速解决。但是请注意，深度优先搜索一般不能应用于求解最优解的问题上。

// node: 当前在回溯树中的结点
void trace (int node){if (当前结点 == 目标结点)输出方案;else{尝试所有满足条件的结点if (新结点符合条件){记录新结点;设置占位标志;trace(i+1);  // 进行下一结点的试探删除新结点;恢复占位标志;}}
}

接下来的例子将带领大家由浅入深、循序渐进走入回溯法的世界。

1. 走楼梯

【描述】楼梯有 n 级台阶（n ≤ 20），可以一步走 1 级，也可以一步走 2 级。输入一个正整数 n，请输出所有上楼梯的方案。

【输入和输出样例】

5
方案：1 1 1 1 1
方案：1 1 1 2
方案：1 1 2 1
方案：1 2 1 1
方案：1 2 2
方案：2 1 1 1
方案：2 1 2
方案：2 2 1

【简要算法描述】

• 设置一个数组 record 记录每一次的走法（走一级台阶还是两级台阶？）
• 设置一个变量 passed 记录走过的台阶数

// 第node步的试探：我该走一级台阶还是两级台阶？
void trace (int node){if (passed == 目标台阶数)输出方案;else{尝试走step级台阶（step=1,2）if (可以走step级台阶){record[node] = step; // 记录passed = passed + step; // 占位trace(node+1);  // 试探下一步record[node] = 0; // 清除记录passed = passed - step; // 复位}}
}

【题解】

#include <cstdio>
#include <cstring>
using namespace std;// goal:目标台阶数, node:当前在回溯树中的结点/第node步, passed:记录走过的台阶数, record:记录走法方案 
void trace (int goal, int node, int passed, int record[]){if (passed == goal){  // 若正好走到目标台阶 node--;  // 则需修正当前结点printf("方案：");for (int i = 1; i <= node; i++)printf("%d ", record[i]);printf("\n");}else{for (int step = 1; step <= 2; step++){  // 尝试走一个台阶或两个台阶 if (passed + step <= goal){		    // 如果没有超出目标台阶数 record[node] = step;            // 则记录该走法passed += step;					// 并记录走过的台阶数（相当于占位） trace(goal, node+1, passed, record);  // 继续探索下一种走法，试探下一步该怎么走 record[node] = 0;               // 回溯，删除该走法（非必要操作） passed -= step;					// 回溯，回到没有走这一步之前的台阶上，为尝试下一种走法做准备（相当于恢复占位标志）}	}}
}int main(){int n;int A[100];while (scanf("%d", &n) != EOF){memset(A, 0, sizeof(A));trace(n, 1, 0, A);  // 当前处在回溯树的初始结点，走过的台阶数为0 }return 0;
}

通过该题想必可以了解到回溯算法的套路了，比较关键的无非就是五个步骤。下面的几题跟寻找路径有关，难度比第一题稍小。

2. 机器走格子，但限定方向

【描述】现有一个 4x4 的格子，给定一个起始坐标（m，n），只允许机器人向上或向右到达目标坐标点（4,4），请输出所有的机器人走法方案。

注：4x4 格子的横坐标范围为 1 ~ 4，纵坐标范围为 1 ~ 4，因此 m，n 值只能为 1 ~ 4。

【输入和输出样例 1】

2 3
方案：
0 0 0 0
0 0 1 0
0 0 1 0
0 0 1 1
方案：
0 0 0 0
0 0 1 0
0 0 1 1
0 0 0 1
方案：
0 0 0 0
0 0 1 1
0 0 0 1
0 0 0 1

【输入和输出样例 2】

3 2
方案：
0 0 0 0
0 0 0 0
0 1 0 0
0 1 1 1
方案：
0 0 0 0
0 0 0 0
0 1 1 0
0 0 1 1
方案：
0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1

【简要算法描述】

• 设置一个数组 record 记录每一次的走法

// 当前机器人在坐标point处
void trace (point){if (point == 目标坐标)输出方案;else{尝试向上或向右if (可以向上或向右){record[point+向上或向右] = 1;trace(point+向上或向右);  // 试探下一步record[point+向上或向右] = 0;}}
}

【题解】

#include <cstdio>
#include <cstring>
using namespace std;struct Pos{  // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符== bool operator == (const struct Pos &p){return p.x == x && p.y == y; }// 重载运算符<=bool operator <= (const struct Pos &p){return x <= p.x && y <= p.y; } // 重载运算符+，用于坐标点之间的运算 struct Pos operator + (const struct Pos &p){return Pos(x+p.x, y+p.y);}
};#define MAX 4
int A[MAX+1][MAX+1] = {0};  // 记录走法方案，也兼具占位功能，1表示走过，0表示没走过 
struct Pos delta[2] = {Pos(1, 0), Pos(0, 1)};  // 只能向右走或向上走，用于改变 // goal:目标坐标, point:当前坐标, record:记录走法方案 
void trace (struct Pos goal, struct Pos point, int record[][MAX+1]){if (point == goal){  					// 若正好走到目标点，则输出方案 printf("方案：\n");for (int i = 1; i <= MAX; i++){for (int j = 1; j <= MAX; j++)printf("%d ", record[i][j]);printf("\n");}}else{for (int i = 0; i <= 1; i++){  							// 尝试向上或向右走 if (point + delta[i] <= Pos(MAX, MAX)){  			// 如果没有走出范围以外 struct Pos pointDelta = point + delta[i];record[pointDelta.x][pointDelta.y] = 1;         // 则记录该走法（或标记占位标志） trace(goal, pointDelta, record);     			// 继续探索下一种走法，遍历过的结点数加1 record[pointDelta.x][pointDelta.y] = 0;       	// 回溯，为尝试下一种走法做准备（或恢复占位标志） }	}}
}int main(){int m, n;while (scanf("%d%d", &m, &n) != EOF){struct Pos init(m, n);struct Pos goal(MAX, MAX);memset(A, 0, sizeof(A));A[init.x][init.y] = 1; // 起始点标记为走过 trace(goal, init, A);  // 当前处在回溯树的初始结点，走过的台阶数为0 printf("\n");}return 0;
}

3. 中国象棋，马走日字

【描述】中国棋盘大小为 8x9，假设马的初始位置在（0,0）处，现给定象棋棋盘中的一个点（m，n），请输出跳到（m，n）的总步数小于十步之内的方案，需要标出第几步走到了棋盘的哪个位置。

注意，由于遍历所有方案所用的时间已超出了可接受范围，因此请每输出一个方案使用system(“pause”)暂停程序运行。

【输入和输出示例】

3 3
方案：1  0  0  0  3  0  7  0  50  0  2  0  8  0  4  0  00  0  0  0  0  0  0  6  00  0  0  9  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  0
请按任意键继续. . .
方案：1  0  0  0  3  0  7  0  50  0  2  0  0  0  4  0  00  0  0  0  0  8  0  6  00  0  0  9  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  0
请按任意键继续. . .
方案：1  0  0  0  3  0  0  0  50  0  2  0  8  0  4  0  00  0  0  0  0  0  0  6  00  0  0  9  0  7  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  00  0  0  0  0  0  0  0  0
请按任意键继续. . .

【简要算法描述】

• 设置一个数组 record 记录每一次的走法

// 当前马走到坐标point处，为第step步
void trace (point, step){if (point == 目标坐标)输出方案;else{从point开始，尝试下一步日字，得到新坐标if (新坐标可以走){record[新坐标] = step;trace(新坐标, step+1);  // 试探下一步record[新坐标] = 0;}}
}

【题解】

#include <cstdio>
#include <cstring>
#include <stdlib.h>
using namespace std;struct Pos{  // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符== bool operator == (const struct Pos &p){return p.x == x && p.y == y; }// 重载运算符<=bool operator <= (const struct Pos &p){return x <= p.x && y <= p.y; } // 重载运算符+，用于坐标点之间的运算 struct Pos operator + (const struct Pos &p){return Pos(x+p.x, y+p.y);}
};#define MAX_X 8
#define MAX_Y 9
int A[MAX_X][MAX_Y];  // 记录走法方案，也兼具占位功能，非0表示走过，0表示没走过 
struct Pos delta[8] = { Pos(-2, 1), Pos(-1, 2), Pos(1, 2), Pos(2, 1),Pos(-2, -1), Pos(-1, -2), Pos(1, -2), Pos(2, -1)};  // goal:目标坐标, point:当前坐标, record:记录走法方案, step:记录走了多少步 
void trace (struct Pos goal, struct Pos point, int record[][MAX_Y], int step){if (step > 11)return;if (point == goal && step <= 11){  					// 若正好走到目标点，则输出方案 printf("方案：\n");for (int i = 0; i < MAX_X; i++){for (int j = 0; j < MAX_Y; j++)printf("%3d", record[i][j]);printf("\n");}system("pause");  // 不可能遍历所有方案，因此每输出一个方案暂停一下}else{for (int i = 0; i < 8; i++){  	struct Pos pointDelta = point + delta[i];			// 尝试不同的走法 if (Pos(0, 0) <= pointDelta && pointDelta <= Pos(MAX_X-1, MAX_Y-1) && record[pointDelta.x][pointDelta.y] == 0){ 	// 如果没有走出范围以外，以及该点未走过 record[pointDelta.x][pointDelta.y] = step;      // 则记录该走法（或标记占位标志） trace(goal, pointDelta, record, step+1);     	// 继续探索下一种走法，遍历过的结点数加1 record[pointDelta.x][pointDelta.y] = 0;       	// 回溯，为尝试下一种走法做准备（或恢复占位标志） }	}}
}int main(){int m, n;while (scanf("%d%d", &m, &n) != EOF){struct Pos init(0, 0);struct Pos goal(m, n);memset(A, 0, sizeof(A));A[0][0] = 1; // 起始点标记为第一步 trace(goal, init, A, 2);  // 从第二步开始走printf("\n");}return 0;
}

4. 走迷宫

【描述】给一张 6x6 迷宫地图，用“.”表示可以走的路，用“#”表示障碍物，以左上角（0,0）为起点，左下角（5,5）为终点，输出所有路径方案，用“Y”标记已经走过的路径。

【输入示例】

.#..#.
.##.#.
..#...
#...#.
.#.#..
#.....

【输出示例】

方案：
Y # . . # .
Y # # . # .
Y Y # . . .
# Y Y . # .
. # Y # . .
# . Y Y Y Y方案：
Y # . . # .
Y # # . # .
Y Y # . . .
# Y Y . # .
. # Y # Y Y
# . Y Y Y Y方案：
Y # . . # .
Y # # . # .
Y Y # Y Y Y
# Y Y Y # Y
. # . # . Y
# . . . . Y方案：
Y # . . # .
Y # # . # .
Y Y # Y Y Y
# Y Y Y # Y
. # . # Y Y
# . . . Y Y

【简要算法描述】

• 将迷宫地图当做可以标记占位的数组
• 注意，如果将迷宫地图定义为由 6 个字符串组成，则每个字符串最后的“\0”也要占位，所以申请数组时请申请 6x7 的大小

// 当前走到坐标point处
void trace (point){if (point == 目标坐标)输出方案;else{从point开始尝试下一步，得到新坐标if (新坐标没有超出范围，且不是障碍){record[新坐标] = 'Y';trace(新坐标, step+1);  // 试探下一步record[新坐标] = 0;}}
}

【题解】

#include <cstdio>
#include <cstring>
using namespace std;struct Pos{  // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x, int _y): x(_x), y(_y) {}// 重载运算符== bool operator == (const struct Pos &p){return p.x == x && p.y == y; }// 重载运算符<=bool operator <= (const struct Pos &p){return x <= p.x && y <= p.y; } // 重载运算符+，用于坐标点之间的运算 struct Pos operator + (const struct Pos &p){return Pos(x+p.x, y+p.y);}
};#define MAX_X 6
#define MAX_Y 6
char A[MAX_X][MAX_Y+1] = {".#..#.",".##.#.","..#...","#...#.",".#.#..","#....."};  struct Pos delta[4] = {Pos(1, 0), Pos(0, 1), Pos(-1, 0), Pos(0, -1)};  // goal:目标坐标, point:当前坐标, record:记录走法方案
void trace (struct Pos goal, struct Pos point, char record[][MAX_Y+1]){if (point == goal){  					// 若正好走到目标点，则输出方案 printf("方案：\n");for (int i = 0; i < MAX_X; i++){for (int j = 0; j < MAX_Y; j++)printf("%c ", record[i][j]);printf("\n");}printf("\n");}else{for (int i = 0; i < 4; i++){  	struct Pos pointDelta = point + delta[i];			// 尝试不同的走法 if (Pos(0, 0) <= pointDelta && pointDelta <= Pos(MAX_X-1, MAX_Y) && record[pointDelta.x][pointDelta.y] == '.'){ 		// 如果没有走出范围以外，以及该点未走过或不是障碍 record[pointDelta.x][pointDelta.y] = 'Y';      		// 则记录该走法（或标记占位标志） trace(goal, pointDelta, record);     				// 继续探索下一种走法record[pointDelta.x][pointDelta.y] = '.';       	// 回溯，为尝试下一种走法做准备（或恢复占位标志） }	}}
}int main(){int m, n;struct Pos init(0, 0);struct Pos goal(5, 5);A[0][0] = 'Y'; // 起始点标记为走过 trace(goal, init, A);  printf("\n");return 0;
}

5. 积木覆盖

【描述】给定一个 6x6 的网格，用“#”表示被某块积木占用，用“.”表示没有被积木占用，请求出网格中一共有多少块积木，并输出每块积木的坐标。

【输入样例 1】

.#..#.
.#.##.
.#....
#...#.
.#.###
#....#

【输出样例 1】

第1块积木坐标：(1,1) (2,1) (0,1)
第2块积木坐标：(1,4) (0,4) (1,3)
第3块积木坐标：(3,0)
第4块积木坐标：(4,4) (4,5) (5,5) (3,4) (4,3)
第5块积木坐标：(4,1)
第6块积木坐标：(5,0)
共有6块积木

【输入样例 2】

.#..#.
.####.
.#....
#...#.
.#.###
#....#

【输出样例 2】

第1块积木坐标：(1,1) (2,1) (1,2) (1,3) (1,4) (0,4) (0,1)
第2块积木坐标：(3,0)
第3块积木坐标：(4,4) (4,5) (5,5) (3,4) (4,3)
第4块积木坐标：(4,1)
第5块积木坐标：(5,0)
共有5块积木

【分析】该题比“走迷宫”较简单，但相较于“走迷宫”，本题没有明显的递归回溯终止目标，因为这个目标是隐含的：当一块积木的所有格子都走完后，就代表回溯完毕。本题可以模仿“走迷宫”，先找出被积木占用的格子，即先找到“#”的坐标（相当于迷宫的入口，或某块积木的“入口”），然后开始寻找其他与之相邻的“#”，把“.”视为障碍物，把找到的“#”改为“Y”。

然而这里有个问题。如果回溯时把已走过的“Y”改回“#”，则下一次找到另一个“#”的坐标（相当于某块积木的“入口”），你如何保证是不是之前我们遍历过的同一块积木？所以我们不能把已走过的“Y”改回“#”，而是要改成别的符号，比如“V”，这样才能区分出哪块积木已经遍历过了，下一次就不用遍历了。

【简要算法描述】

// 当前走到坐标point处
void trace (point, map){从point开始尝试下一步，得到新坐标if (新坐标没有超出范围，且新坐标==“#”或“V”){map[新坐标] = 'Y';输出坐标;trace(新坐标, step+1);  // 试探下一步map[新坐标] = 'V';}}
}

【题解】

#include <cstdio>
#include <cstring>
using namespace std;struct Pos{  // 横坐标x和纵坐标y封装为一个 坐标点 结构体 int x;int y;Pos(int _x = 0, int _y = 0): x(_x), y(_y) {}// 重载运算符== bool operator == (const struct Pos &p){return p.x == x && p.y == y; }// 重载运算符<=bool operator <= (const struct Pos &p){return x <= p.x && y <= p.y; } // 重载运算符+，用于坐标点之间的运算 struct Pos operator + (const struct Pos &p){return Pos(x+p.x, y+p.y);}
};#define MAX_X 6
#define MAX_Y 6
// 积木地图 
char A[MAX_X][MAX_Y+1] = {".#..#.",".#.##.",".#....","#...#.",".#.###","#....#"};  // 记录一块积木的每个坐标
struct Pos record[MAX_X * MAX_Y]; // 方向变化数组 
struct Pos delta[4] = {Pos(1, 0), Pos(0, 1), Pos(-1, 0), Pos(0, -1)}; // point:当前坐标, map:标记了占位的地图, isOther:标记该积木除了占有该格子外没有别的格子 
void trace (struct Pos point, char map[][MAX_Y+1], bool &isOther){for (int i = 0; i < 4; i++){  	struct Pos pointDelta = point + delta[i];			// 尝试不同的走法if (Pos(0, 0) <= pointDelta && pointDelta <= Pos(MAX_X-1, MAX_Y)&& map[pointDelta.x][pointDelta.y] == '#' || map[pointDelta.x][pointDelta.y] == 'V'){ // 如果没有走出范围以外，以及该点未走过 map[pointDelta.x][pointDelta.y] = 'Y';      	// 则标记占位标志 isOther = true;									// 这块积木原来还占有别的格子 printf("(%d,%d) ", pointDelta.x, pointDelta.y); // 输出该格子的坐标 trace(pointDelta, map, isOther);     			// 继续探索下一块积木map[pointDelta.x][pointDelta.y] = 'V';       	// 回溯，恢复占位标志}	}
}int main(){int cnt = 0;bool isOther;for (int i = 0; i < MAX_X; i++){for (int j = 0; j < MAX_Y; j++){if (A[i][j] == '#'){  // 找到积木的入口 cnt++;isOther = false;printf("第%d块积木坐标：", cnt);trace(Pos(i, j), A, isOther);  // 开始寻找该积木的其他格子 if (!isOther)  // 如果该积木只占有一个格子，则只输出该格子的坐标 printf("(%d,%d)", i, j);printf("\n");}	}}	printf("共有%d块积木\n", cnt);return 0;
}

从下一篇开始，是有关数学智力题的回溯算法应用。