_{*本篇文章涉及較多知識點，可以在下面查看對應的教程：
遞歸基礎 / 遞歸進階 / 遞歸練習1 / 遞歸練習2 / DFS1 / DFS2 / 回溯算法 / DFS3}

一、遞歸

1. 變化的數

有一個數 $a$，想把這個數變成 $b$，為此可以做兩種變換：

① $x$ 變為 $2x$
② $x$ 變為 $10x+1$
例如：2 -> 4 -> 8 -> 81 -> 162

你需要判斷一下，把 $a$ 變成 $b$ 的是否可能，可能則輸出 YES，否則輸出 NO。

#include <iostream>
using namespace std;// 遞歸判斷是否存在變換路徑
bool transform(int a, int b)
{if (a == b) return 1; // 當 a 和 b 相等時，變換成功，返回 trueif (a > b) return 0; // 當 a 大于 b 時，無法變換，返回 falsereturn transform(a*2, b) || transform(a*10+1, b); // 遞歸進行兩種變換判斷
}int main()
{int a, b;cin >> a >> b;cout << (transform(a, b) ? "YES" : "NO"); // 輸出是否存在變換路徑return 0;
}

2. 數字分解

一個正整數，可以分解成多個大于等于 $1$ 的整數之和的形式，要求這些數字從左向右是遞增的（即后一個數小于等于前一個數）。請你求出對于一個整數 $n$，一共有多少種分解方案。

#include <iostream>
using namespace std;int n;int f(int n, int maxn)
{if (n == 0) return 1;int cnt = 0;for (int i = 1; i <= maxn && i <= n; i++){cnt += f(n-i, i);}return cnt;
}int main()
{cin >> n;cout << f(n, n);
}

二、DFS

1. 八個方向的迷宮

給定一個 $n$ 行 $m$ 列的迷宮，有些格子可以走，有些有障礙物不能到達。每步可以走到周圍 $8$ 個方向的格子中。請你判斷，是否能從左上角走到右下角。如果能走到輸出 YES，否則輸出 NO。

同樣地，不撞南墻不回頭，記得將偏差值改一下就好了。

#include <iostream>
#include <cstdio>
using namespace std;int n, m; // 迷宮大小
bool flag; // 是否有解 
char Map[25][25]; // 地形圖
bool vis[25][25]; // 標記是否走過 
int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 八個方向的偏移量 
int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 八個方向的偏移量 void dfs(int x, int y)
{// 到終點 if (x == n && y == m){flag = true;return;}// 遍歷方向，判斷是否滿足條件for (int i = 0; i < 8; i++){int tmpX = x + dx[i];int tmpY = y + dy[i];// 是通路if (Map[tmpX][tmpY] == '.'){// 未到邊界if (tmpX >= 1 && tmpX <= n && tmpY >= 1 && tmpY <= m) {// 未訪問if (vis[tmpX][tmpY] == false) {vis[tmpX][tmpY] = true;dfs(tmpX, tmpY);}}}}
}int main()
{freopen("map.in", "r", stdin);freopen("map.out", "w", stdout);// 輸入cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> Map[i][j];}}// dfsvis[1][1] = 1;dfs(1, 1);// 輸出	cout << (flag ? "YES" : "NO");fclose(stdin);fclose(stdout);return 0;
}

2. n 皇后

題目描述

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
$n$ 皇后問題研究的是如何將 $n$ 個皇后放置在 $n\times n$ 的棋盤上，并且使皇后彼此之間不能相互攻擊。
給你一個整數 $n$，求出所有不同的 $n$ 皇后問題的解決方案。
每一種解法包含一個不同的 $n$ 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

輸入描述

僅一行，一個正整數 $n$。

輸出描述

若干行，$n\times n$ 的棋盤所有的解，每個解用空格隔開

樣例1

輸入

4

輸出

.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

提示

$4\le n\le 18$

思路：這是根據《C++知識點總結(37)：回溯算法》中第四節的題目改編而來。我們可以知道，按照題目所描述的方法，我們應該使得：

• 每一行都只有一個皇后
• 每一列都只有一個皇后
• 每一個正對角線都只有一個皇后
• 每一個負對角線都只有一個皇后

#include <iostream>
using namespace std;int n;
bool a[20][20];
bool row[20];
bool col[20];
bool zd[40], fd[40];void dfs(int r)
{if (r > n){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (a[i][j]){cout << "Q";}else{cout << ".";}}cout << endl;}cout << endl;return;}for (int j = 1; j <= n; j++) // 遍歷每個列{if (!a[r][j] && !row[r] && !col[j] && !zd[r+j] && !fd[r-j+n]) // 是否沒有沖突{a[r][j] = true;row[r] = true;col[j] = true;zd[r+j] = true;fd[r-j+n] = true;dfs(r+1);a[r][j] = false;row[r] = false;col[j] = false;zd[r+j] = false;fd[r-j+n] = false;}}
}int main()
{cin >> n;dfs(1);return 0;
}

3. 玩具蛇

題目描述

小藍有一條玩具蛇，一共有 $n^2$ 節，上面標著數字1至 $n^2$，每一節都是一個正方形的形狀，相鄰的兩節可以成直線或者成直角。
小藍還有一個 $n\times n$ 的方格盒子，用于存放玩具蛇，盒子的方格上依次標著字母共 $n^2$ 個字母。
小藍可以折疊自己的玩具蛇放到盒子里面。他發現，有很多種方案可以將玩具蛇放進去。
請幫小藍計算一下，總共有多少種不同的方案。如果存在玩具蛇的某一節放在了盒子的不同格子里，則認為是不同的方案。

輸入描述

一個整數 $q$，表示輸入 $q$ 組方格盒子。
接下來 $q$ 行，每行代表一個 $n\times n$ 的方格盒子。

輸出描述

$q$ 個整數表示每個方格盒子的方案數。

樣例1

輸入

2
2
4

輸出

8
552

提示

$1\le n\le 5$

#include <iostream>
#include <cstring>
using namespace std;int q; // 輸入的組數
int n; // 盒子的邊長
bool vis[10][10]; // 盒子是否被占據
int total; // 方案數量
int dx[5] = {-1, 0, 1, 0};
int dy[5] = {0, 1, 0, -1};void dfs(int x, int y, int cnt)
{if (cnt == n*n){total++;return;}for (int i = 0; i < 4; i++){int tx = x+dx[i];int ty = y+dy[i];if (tx>=1 && tx<=n && ty>=1 && ty<=n){if (vis[tx][ty] == 0){vis[tx][ty] = 1;dfs(tx, ty, cnt+1);vis[tx][ty] = 0;}}}
}int main()
{// 輸入cin >> q;for (int i = 1; i <= q; i++){cin >> n;total = 0;memset(vis, 0, sizeof(vis));// dfsfor (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){vis[i][j] = 1;dfs(i, j, 1);vis[i][j] = 0;}}// 輸出cout << total << endl;}return 0;
}

4. 深度優先搜索順序

題目描述

給定一個 $n$ 行 $m$ 列的迷宮，有些格子可以走，有些有障礙物不能到達。每步可以走到上下左右的格子中。請你輸出從左上角（第一行第一列）開始深度優先搜索所有格子的順序。其中，從一個格子出發，優先出發的順序為：上、下、左、右，每個格子只遍歷一次,即按搜索順序輸出從左上角開始能夠搜索到的所有位置。

輸入描述

第一行有兩個正整數 $n$ 和 $m$，表示迷宮的行數和列數。
接下來 $n$ 行為輸入這個迷宮，每行為一個長度為 $m$ 的字符串。第 $i$ 行第 $j$ 列的字符為 '*' 表示迷宮第 $i$ 行第 $j$ 列的格子有障礙物，為 '.' 表示沒有障礙物。

輸出描述

若干行，按遍歷順序在每行輸出搜索到的格子。第 $x$ 行第 $y$ 列的格子以 "(x,y)" 的格式輸出。

樣例1

輸入

3 3
.*.
...
***

輸出

(1,1)
(2,1)
(2,2)
(2,3)
(1,3)

提示

$1\le n,m\le 100$

#include <iostream>
using namespace std;int n, m;
char a[105][105];
bool vis[105][105];
int dx[5] = {-1, 1, 0, 0};
int dy[5] = {0, 0, -1, 1};
int pos = 1;
int ansx[10005];
int ansy[10005];void dfs(int x, int y)
{cout << "(" << x << "," << y << ")\n";for (int i = 0; i <= 3; i++){int tx = x+dx[i];int ty = y+dy[i];if (a[tx][ty] == '.'){if(tx>=1 && tx<=n && ty>=1 && ty<=m){if (vis[tx][ty] == 0){vis[tx][ty] = 1;dfs(tx,ty);}}}}
}int main()
{// 輸入cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}// dfsvis[1][1] = 1;dfs(1, 1);return 0;
}

5. 單詞消消樂

題目描述

給定一個 $n\times n$ 的字母方陣和一個字符串單詞，內可能含有多個這樣的單詞，單詞在方陣中是沿著同一方向連續擺放的，擺放可沿著 $8$ 個方向的任一方向，同一單詞擺放時不再改變單詞方向，單詞與單詞之間可以交叉，因此可能共用字母，輸出時，將不是單詞的字母用 '*' 代替，以凸顯單詞。

輸入描述

輸入文件名word.in。
第一行一個數 $n$，表示字母方陣的大小（$7\le n\le 100$），第二行開始輸入 $n\times n$ 的字母方陣，字母間沒有空格。
最后一行輸入一個字符串單詞，單詞長度在 $1$ 到 $15$ 之間。

輸出描述

輸出文件名word.out。
突出顯示單詞的 $n\times n$ 字母方陣。

樣例1

輸入

4
abcd
fesh
eawj
qbso
ab

輸出

ab**
****
*a**
*b**

提示

題中所有字母均為小寫

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;int n;
int pos;
char a[120][120];
int dx[10] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[10] = {-1, 0, 1, -1, 1, -1, 0, 1};
string s;
int px[120], py[120];
bool vis[120][120];void dfs(int x, int y, int h)
{if (pos == s.length()) // 邊界{for (int i = 0; i < pos; i++){vis[px[i]][py[i]] = 1;}return;}int tx = x + dx[h];int ty = y + dy[h];if (tx >= 1 && tx <= n && ty >= 1 && ty <= n && a[tx][ty] == s[pos]){px[pos] = tx;py[pos] = ty;pos++;dfs(tx, ty, h);}
}int main()
{freopen("word.in", "r", stdin);freopen("word.out", "w", stdout);// 輸入cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}cin >> s;// 找到開頭字符for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (a[i][j] == s[0]){for (int h = 0; h <= 7; h++){pos = 0;// memset(px, 0, sizeof(px));// memset(py, 0, sizeof(py));px[0] = i;py[0] = j;pos++;dfs(i, j, h);}}}}// 輸出for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (vis[i][j]){cout << a[i][j];}else{cout << "*";}}cout << endl;}fclose(stdin);fclose(stdout);return 0;
}

6. 奇怪的系統

題目描述

原本平靜的生活被打破，你被卷入一場神秘的案件中，成為偵探團的一員，由于你自帶解謎系統，所以解決案件對你來說小菜一碟，但系統有一個神奇的地方，只有給出滿足要求的案件物品，系統才能給出線索，每個案件物品都有線索值，因此組合得到的線索也不一樣。
現在你面前有 $n$ 個不同線索值的案件物品，系統需要的線索值為 $m$，每給出一組不同的物品組合使線索值總和剛好為 $m$ 則可以得到一條新的線索，并且物品不會因為給系統而消失，為了解開這個謎團，你需要選擇合適數量與線索值的案件物品給系統，以此得到不同的線索，你一共能夠得到多少條線索呢？

輸入描述

第一行輸入 $n$ 和 $m$，第二行一共 $n$ 個數字，表示每個案件物品的線索值 $a_i$。

輸出描述

輸出能夠得到的線索條數。

樣例1

輸入

3 40 
20 20 20

輸出

3

提示

【樣例解釋】
一共 $3$ 個物品，線索值分別為 $20,20,20$
系統需要的線索值為 $40$，則可以 $1,2$ 組合，$1,3$ 組合，$2,3$ 組合剛好都為 $40$，$1,2,3$ 組合超過 $40$ 不符合，所以得到 $3$ 條線索。
【數據范圍】
$0<m\le 100，1\le n\le 20，a_i\le m$

#include <iostream>
using namespace std;int n, m;
int cnt;
int a[25];
bool used[25];// 判斷選擇的數字之和是否等于預設值
bool check()
{// 求和 int sum = 0;for (int i = 1; i <= n; i++){if (used[i]){sum += a[i];}}// 判斷是否等于預設值if (sum == m){return true;}return false;
}// pos: 當前位置
// cnt: 選的數字個數 
void dfs(int pos)
{if (pos > n) // 邊界{if (check()) // 題目條件{cnt++;}return;}dfs(pos+1); // 不選used[pos] = 1; // 標記dfs(pos+1); // 選 used[pos] = 0; // 回溯
}int main()
{// 輸入 cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}// dfsdfs(1);// 輸出cout << cnt; return 0;
}

7. [USACO23JAN] Air Cownditioning II B

參觀一下某谷吧。

#include <iostream>
using namespace std;int n, m, k;
int ans = 1e9;
int cw[105], s[25], t[25], c[25], a[25], b[25], p[25], v[25];bool check() // 是否滿足條件
{for(int i = 1; i <= k; i++){if (cw[i] > 0){return false;}}return true;
}void dfs(int pos, int s)
{if (pos > m){if (check()){ans = min(ans, s);//滿足條件，更新答案}return;}dfs(pos+1, s); // 不選// 標記for(int i = a[pos]; i <= b[pos]; i++)cw[i] -= p[pos];dfs(pos+1, s+v[pos]); // 選// 回溯for(int i = a[pos]; i <= b[pos]; i++)cw[i] += p[pos];
}int main()
{// 輸入cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i] >> t[i] >> c[i];k = max(k, t[i]);for (int j = s[i]; j <= t[i]; j++){cw[j] += c[i]; //事先處理}}for (int i = 1; i <= m; i++)cin >> a[i] >> b[i] >> p[i] >> v[i];// dfsdfs(1, 0);// 輸出cout << ans;return 0;
}

三、排列組合

選擇同學

題目描述

今有 $n$ 位同學，可以從中選出任意名同學參加合唱。
請輸出所有可能的選擇方案。

輸入描述

僅一行，一個正整數 $n$。

輸出描述

若干行，每行表示一個選擇方案。
每一種選擇方案用一個字符串表示，其中第 $i$ 位為 $Y$ 則表示第 $i$ 名同學參加合唱；為 $N$ 則表示不參加。

樣例1

輸入

3

輸出

NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY

提示

$1\le n\le 10$

思路：這是非常典型的一道回溯題，與《C++知識點總結(37)：回溯算法》中第二節的第一小節比較類似。因為這道題目只有 $Y$ 和 $N$ 兩種可能，所以在深度優先搜索的時候，我們只需要用兩個遞歸就可以，不需要 for 循環了。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;int n;
string s;void dfs(int pos, string s)
{if (pos > n){cout << s << endl;return;}dfs(pos+1, s+'N');dfs(pos+1, s+'Y');
}int main()
{cin >> n;dfs(1, s);return 0;
}

四、剪枝優化

1. 走迷宮

題目描述

在一個神秘的迷宮中，有一個勇敢的冒險家，他的目標是從起點 $(1,1)$ 走到終點 $(n,n)$。但是，這個迷宮并不是那么容易通過的，有些地方是可以走的，有些地方是惡龍所在的區域。為了成功通過迷宮，冒險家必須遵循以下規則：

1. 只能向下、右兩個方向移動；
2. 在移動過程中，可以至多轉向 $k$ 次。
   如果一條路線中冒險家經過了某個方格而另一條路線中沒有，則認為這兩條路線不同。
   現在，你需要幫助這位勇敢的冒險家，計算他從起點到終點的方案數。

輸入描述

輸入文件名maze.in。
第一行包含三個整數 $n,k,m$，表示矩陣的大小，轉向次數和障礙物的數量。
接下來 $m$ 行，每行包含兩個整數 $x$ 和 $y$，表示第 $x$ 行第 $y$ 列是障礙物。

輸出描述

輸出文件名maze.out。
輸出一個整數，表示從起點到終點的方案數，方案數可能為 $0$（那就算給惡龍飽餐一頓了 ）。

樣例1

輸入

5 2 2
2 2
3 4

輸出

4

提示

$1\le n\le 50$
$1\le k\le 5$
$1\le m\le 100$

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;int n, k, m;
int cnt;
bool a[60][60];
int dx[5] = {0, 1};
int dy[5] = {1, 0};void dfs(int x, int y, int turn, int direc)
{if (x == n && y == n) // 到達終點 {if (turn <= k){cnt++;}return;}// 剪枝 if (turn > k){return;}if (turn == k){if (x != n && y != n){return;}}// 遞歸 for (int i = 0; i <= 1; i++){int tx = x + dx[i];int ty = y + dy[i];// 是通路if (a[tx][ty] == 1){// 未到邊界if (tx >= 1 && tx <= n && ty >= 1 && ty <= n) {// 是否轉彎 if (i != direc && direc != -1){dfs(tx, ty, turn+1, i);}else{dfs(tx, ty, turn, i);}}}}
}int main()
{freopen("maze.in", "r", stdin);freopen("maze.out", "w", stdout);// 初始化迷宮（默認都是通路）memset(a, 1, sizeof(a));// 輸入cin >> n >> k >> m;for (int i = 1; i <= m; i++){int x, y;cin >> x >> y;a[x][y] = 0;}// dfsdfs(1, 1, 0, -1);cout << cnt;fclose(stdin);fclose(stdout);return 0;
}

2. 危險的工作

題目描述

在一個神秘的島嶼上，有 $N$ 個勇士需要分擔 $N$ 個危險的工作。每個勇士都有自己的特長，可以擔任其中一項工作。每個工作都有一個危險值，代表完成這項工作的風險程度。每個勇士擔任工作時，會承擔該工作的危險值。現在，你需要為這些勇士分配工作，使得每個勇士承擔的危險值之和最小。

輸入描述

第一行輸入一個整數 $N$，代表勇士的數量。
接下來 $N$ 行，每行輸入 $N$ 個整數，第 $i$ 行的 $N$ 個數字分別代表第 $i$ 個勇士擔任 $1?N$ 項工作的危險值，用空格隔開。

輸出描述

輸出一個整數，代表每個勇士承擔的危險值之和的最小值。

樣例1

輸入

3
1 2 3
4 5 6
7 8 9

輸出

15

提示

$1\le N\le 11$
$1\le$ 危險值 $\le 100$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;int n;
int d[20][20];
int mind = 1e8;
int a[20];
bool vis[20];void dfs(int pos, int total)
{if (pos > n) // 邊界{mind = min(mind, total);return;}for (int i = 1; i <= n; i++){if (!vis[i]) // 檢查位置是否被占用{vis[i] = true;a[pos] = i; // 標記int new_total = total + d[pos][i];if (new_total <= mind) // 剪枝dfs(pos + 1, new_total); // 遞歸下一個位置a[pos] = -1; // 回溯vis[i] = false;}}
}int main()
{// 初始化memset(a, -1, sizeof(a));memset(vis, false, sizeof(vis));// 輸入cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> d[i][j];// dfsdfs(1, 0);// 輸出cout << mind;return 0;
}

3. 規定時間走迷宮

第一行給定迷宮的大小 $n,m$ 和規定時間 $t$，表示有一個 $n\times m$ 的迷宮，起點到終點正好是規定時間（每向某個方向走一格，就算 $1s$）。
接下來 $n$ 行每行 $m$ 個空格隔開的字符，'.' 代表空地，'*' 代表障礙。
最后一行給定初始位置和終點位置 $sx,sy,ex,ey$。
求你求出符合規定時間的路徑數。
數據范圍：$1\le n,m\le 100$

#include <iostream>
#include <cmath>
using namespace std;int n, m, t, sx, sy, ex, ey, cnt;
char a[105][105];
bool vis[105][105];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};void dfs(int x, int y, int l)
{// 剪枝if (abs(ex-x)+abs(ey-y) > t-l || l>t)return;// 邊界if (x==ex && y==ey && l==t){cnt++;return;}for (int i = 0; i <= 3; i++) {int nx = x+dx[i];int ny = y+dy[i];if (nx>=0 && nx<=n && ny>=0 && ny<=m) // 未到邊界{if (vis[nx][ny]==0 && a[nx][ny]=='.') // 未訪問、是空地{vis[nx][ny] == 1;dfs(nx, ny, l+1);vis[nx][ny] == 0;}}}
}int main()
{// 輸入cin >> n >> m >> t;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}cin >> sx >> sy >> ex >> ey;// dfsdfs(sx, sy, 0);// 輸出cout << cnt;return 0;
}