拯救大兵雷诺（递归＋回溯）

本文主要是介绍拯救大兵雷诺（递归＋回溯），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

新晋的星灵大主教Artanis在目睹了挚友Zeratul的牺牲之后决心对抗黑暗之神Amon。为此，他首先要团结全星区所有种族的力量。

坚定的盟友雷诺和他刚刚结束了Arcturus统治的Terran帝国正在遭受Amon控制的异虫的攻击，帮助他们即可在日后对抗Amon的时候获得帮助。

当星灵部队抵达时，人类的战线已经崩溃，Artanis预测，如果没有星灵的帮助，人类部队将在n单位时间之后彻底战败。异虫部队在战场上建立了m个据点，编号从1到m，要想帮助人类取得胜利，必须击破全部的m个据点。Artanis还预测出了击破第i个据点所需的时间Ti，同时，击破第i个据点会导致异虫的攻势减弱，人类战败的倒计时会增加Ci单位时间。此外，Artanis还计算出了星灵部队战场上任意两点间移动所需的时间Ai,j表示从第i个据点到第j个据点所需的单位时间，0 <= i, j <= m，0表示星灵部队的大本营。

由于Artanis作为大主教还是个新人，指挥能力还不足以发动多线作战，因此他只能从大本营出发，一个一个地摧毁异虫的据点。他现在想知道，在保证人类部队不全军覆没的前提下，有多少种不同的进攻顺序？

输入格式

输入包括m + 4行：

第1行包括2个整数：n和m

第2行包括m个整数：Ti

第3行包括m个整数：Ci

第4至m+4行（共m+1行）是一个(m+1) * (m+1)整数矩阵：Ai,j

整数之间使用空格分隔

输出格式

输出只包含1个整数，即不同的进攻顺序方案数

输出结尾应有一个换行符

数据规模：

0 < n <= 10000, 0 < m <= 10, 0 < Ti, Ci, Ai,j <= 1000

此外，由于星灵拥有诸多人类无法理解的高端技术，因此在据点之间移动所需的时间Ai,j不一定满足三角形不等式，即不保证满足Ai,j <= Ai,k + Ak,j，也不能保证Ai,j = Aj,i，但是Ai,i一定为0

样例输入：

5 3

1 2 3

3 2 1

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

样例输出：

样例解释：

只有1 2 3和2 1 3的进攻顺序才能保证倒计时始终在0以上

如果按照1 3 2的顺序来进攻的话，进攻1需要1+1 = 2的时间，还剩下3，又增加3变成6；接下来进攻3需要1+3=4的时间，还剩下2，又增加1变成3；最后进攻2需要1+2=3的时间，倒计时变成0，人类战败。

递归+回溯实际上就是遍历所有情况，如果能在当前情况下成功就继续往下走，如果不能就退出来，寻找下一个能实现当前情况的点。
所以在递归函数中要加一个存当前情况的参数

#include <stdio.h>
#include <string.h>
int n, m, t[10] = {0};
int c[10], b[12] = {0};
int a[1000][1000];
int sum = 0, tot;
void rescue(int i, int n, int tot) {int j;if (tot == m) {sum++;return;}b[i] = 1;//用来确定不能重复救同一个点，在不同的递归函数中，b【i】的值是不同的。for (j = 1; j <= m; j++) {if (b[j] == 0 && n - a[i][j] - t[j] > 0) {tot++;rescue(j, n - a[i][j] - t[j] + c[j], tot);b[j] = 0;tot--;}}return;
}
int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= m; i++) {scanf("%d", &t[i]);}for (int i = 1; i <= m; i++) {scanf("%d", &c[i]);}for (int i = 0; i <= m; i++) {for (int j = 0; j <= m; j++) {scanf("%d", &a[i][j]);}}for (int i = 0; i <= m; i++) {tot = 0;rescue(i, n, tot);memset(b, 0, sizeof(b));}printf("%d\n", sum);return 0;
}