💃🏼 本人簡介：男
👶🏼 年齡：18
🤞 作者：那就叫我亮亮叭
📕 專欄：關(guān)于C/C++那點(diǎn)破事

0.0 寫在前面

書接上文，上次我們講到了深搜的思想與經(jīng)典的迷宮問題，這次我們不再細(xì)節(jié)性講解其思想，重在針通過幾道例題來實(shí)踐掌握深搜的用法，歡迎大佬們來指點(diǎn)一二，我們一起加油！！還沒了解的可以直接點(diǎn)進(jìn)行學(xué)習(xí)哦👉👉👉【C++算法】dfs深度優(yōu)先搜索(上) ——【全面深度剖析+經(jīng)典例題展示】

1. 中國象棋

1.1 題干信息

① 背景說明概述

中國象棋博大精深，其中馬的規(guī)則最為復(fù)雜，也是最難操控的一顆棋子。我們都知道象棋中馬走"日"，比如在(2, 4)位置的一個馬【如下圖所示】，跳一步能到達(dá)的位置有(0,3)，(0,5)，(1,2)，(1,6)，(3,2)，(3,6)，(4,3)，(4,5)。

• 注意：上圖中，豎直向下的是x，水平向右的是y！！！

② 問題描述

蒜頭君正在和花椰妹下棋，蒜頭君正在進(jìn)行戰(zhàn)略布局，他需要把在(x, y)位置的馬跳到(x’,
y’)位置，以達(dá)到威懾的目的。但是棋盤大小有限制，棋盤是一個10 x 9的網(wǎng)格，左上角坐標(biāo)為(0,0)，右下角坐標(biāo)為(9,
8)，馬不能走出棋盤，并且有些地方已經(jīng)有了棋子，馬也不能跳到有棋子的點(diǎn)。蒜頭君想知道，在不移動其他棋子的情況下，能否完成他的戰(zhàn)略目標(biāo)。

③ 輸入格式

• 輸入一共10行，每行一個長度為9的字符串。
• 輸入表示這個棋盤，我們用'.'表示空位置，用'#'表示該位置有棋子，用'S'表示初始的馬的位置，用'T'表示馬需要跳到的位置。
• 輸入保證一定只有一個'S'和'T'。

④ 輸出格式

如果在不移動其他棋子的情況下，馬能從'S'跳到'T'，那么輸出一行"Yes"，否則輸出一行"No"。

⑤ 樣例輸入

.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......

⑥ 樣例輸出

Yes

1.2 思路解釋

和上一篇例題的思路基本一模一樣，只不過上次迷宮只能是上下左右走，而這次的象棋中🐎可以走八個方向，只是對x、y坐標(biāo)的改變不同而已，其他基本一致，所以這里就不過多贅述了，不太明白的可以點(diǎn)這里哦【C++算法】dfs深度優(yōu)先搜索(上) ——【全面深度剖析+經(jīng)典例題展示】

大致思路如下：

• ①判斷象棋終點(diǎn)，記錄所走路徑
• ②完善搜索回溯，處理數(shù)組邊界
• ③找尋馬兒起點(diǎn)，打印結(jié)束路徑

1.3 code展示

#include<iostream>
#include<stdio.h>
using namespace std;int n, m;
char pos[105][105];
int trace[105][105];
int dir[8][2] = { {-1 , -2} , {-2 , -1} , {-2 , 1} , {-1 , 2} , {1 , 2} , {2 , 1} , {2 , -1} , {1 , -2} };  // 找出馬兒走"日"時x、y坐標(biāo)變化的所有情況【基本按逆時針來】bool check_in(int x, int y) {	//	判斷數(shù)組是否越界return (x >= 1 && x <= n && y >= 1 && y <= m);   //這里表示的是如果()里為真，則返回true，否則返回false
}bool dfs(int x, int y) {if (pos[x][y] == 'T') {return true;}pos[x][y] = 'x';  //用x記錄路徑trace[x][y] = 1;  //標(biāo)記已走過for (int i = 0; i < 8; i++) {int xx = x + dir[i][0];  //表示x加上第幾個方向的第1個數(shù)，即變化后行的坐標(biāo)int yy = y + dir[i][1];  //表示y加上第幾個方向的第2個數(shù)，即變化后列的坐標(biāo)if (pos[xx][yy] != '#' && check_in(xx, yy) && !trace[xx][yy]) {if (dfs(xx , yy)) {return true;}  }}	pos[x][y] = '.';	//	如果一個位置的上下左右都走不了，則取消該位置的路徑進(jìn)行回溯，回溯過程把之前已標(biāo)記的'x'改回'.'trace[x][y] = 0;		//走不通，則回溯過程標(biāo)記為沒走過return false;
}int main() {cin >> n >> m;//輸入象棋地圖 找🐎兒的起點(diǎn)int x ,  y;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> pos[i][j];if (pos[i][j] == 'S') {x = i, y = j;}}}cout << "--------------------------------" << endl;if (dfs(x , y)) {cout << "Yes!!!" << endl;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cout << pos[i][j];}	cout << endl;}}else {cout << "No!!!" << endl;}return 0;
}

2. 踏青

2.1 題干信息

① 背景說明概述

蒜頭君和他的朋友周末相約去召喚師峽谷踏青。他們發(fā)現(xiàn)召喚師峽谷的地圖是由一塊一塊格子組成的，有的格子上是草叢，有的是空地。草叢通過上下左右4個方向擴(kuò)展其他草叢形成一片草地，任何一片草地中的格子都是草叢，并且所有格子之間都能通過上下左右連通。如果用'#"代表草叢，'.' 代表空地，則下面的峽谷中有2片草地。

##..
..##

② 問題描述

• 處在同一個草地的2個人可以相互看到，空地看不到草地里面的人。他們發(fā)現(xiàn)有一個朋友不見了，現(xiàn)在需要分頭去找，每個人負(fù)責(zé)一片草地，蒜頭君想知道他們至少需要多少人。

③ 輸入格式

• 第一行輸入n,m(1 ≤ n, m <= 100) 表示峽谷大小。接下來輸入n行字符串表示峽谷的地形。

④ 輸出格式

• 輸出至少需要多少人。

⑤ 樣例輸入

5 6
.#....
..#...
..#..#
...##.
.#....

⑥ 樣例輸出

5

2.2 思路解釋

• 根據(jù)題意，最后要求最少人數(shù)，而根據(jù)一人負(fù)責(zé)一片草地，則就轉(zhuǎn)換求最少草地數(shù)，就是該地形最少有多少片土地。我們先輸入地形，再依次遍歷每個格子是否為草地，如果不是草地，直接略過；如果是草地，則是否之前找過，如果找過則還是略過，如果沒找過，則先記錄下已找過，結(jié)果+1，并對該草地的上下左右遍歷是否是未被找的草地【深搜思想】。最后輸出結(jié)果。

2.3 code展示

#include<iostream>
#include<stdio.h>
using namespace std;int n, m, ans = 0;
char pos[105][105];
bool trace[105][105];//法一
//bool check_in(int x, int y) {
//	return (x >= 1 && x <= n && y >= 1 && y <= m);
//}
//
//void dfs(int x, int y) {
//	if (check_in(x, y) && pos[x][y] == '#' && !trace[x][y]) {
//		trace[x][y] = 1;
//		dfs(x, y + 1);
//		dfs(x + 1, y);
//		dfs(x, y - 1);
//		dfs(x - 1, y);
//	}
//}//法二
void dfs(int x, int y) {if (x < 1 || x > n || y < 1 || y > m || trace[x][y] || pos[x][y] == '.') {return;}trace[x][y] = true;dfs(x - 1, y);	  //記錄上面dfs(x , y - 1);  //記錄左面dfs(x + 1, y);   // 記錄下面dfs(x , y + 1);  //記錄右面
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> pos[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (!trace[i][j] && pos[i][j] == '#') {	//	假如是草叢的話且之前沒找過dfs(i, j);	//	把這個位置和周邊草叢標(biāo)記好ans++; //記錄草叢數(shù)量}}}cout << ans << endl;return 0;
}

3. 迷宮解的方案數(shù)

3.1 題干信息

① 背景說明概述

蒜頭君是一個玩迷宮的高手，天下還沒有能難住他的迷宮。但是總有人喜歡習(xí)難蒜頭君，不停的給蒜頭君出難題。這個出題的人很聰明，他知道天下還沒有能難住蒜頭君的迷宮。

② 問題描述

• 所以他便轉(zhuǎn)換思維問蒜頭君，在不走重復(fù)路徑的情況下，總共有多少不同可以到達(dá)終點(diǎn)的路徑呢?蒜頭君稍加思索便給出了答案，你要不要也來挑戰(zhàn)一下?

③ 輸入格式

• 第一行輸入兩個整數(shù)n(1≤n≤11), m(1≤m≤11), 表示迷宮的行和列。然后有一個n*m的地圖，地圖由'.'、'#'、 's' 、'e' 這四個部分組成。'.'表示可以通行的路，'#' 表示迷宮的墻，'s' 表示起始點(diǎn)，'e' 表示終點(diǎn)。

④ 輸出格式

• 輸出一個整數(shù)，表示從's'到達(dá)'e'的所有方案數(shù)。

⑤ 樣例輸入

5 5
s####
.####
.####
.####
....e

⑥ 樣例輸出

1

3.2 思路解釋

• 本題和前面迷宮例題思路差不多，但這個題是要統(tǒng)計到終點(diǎn)的路線的個數(shù)，所以如果能到終點(diǎn)，則需要ans++；如果該節(jié)點(diǎn)的上下左右都行不通，則在四周判斷完后需要清空路徑，trace[x][y]=0，來繼續(xù)探索下一條路。

3.3 code展示

#include<iostream>
#include<stdio.h>
using namespace std;int n, m, ans = 0;
char pos[105][105];
bool trace[105][105];
int dir[4][2] = { {-1, 0},{0,-1},{1,0},{0,1} };bool check_in(int x, int y) {return (x >= 1 && x <= n && y >= 1 && y <= m);
}void dfs(int x, int y) {if (pos[x][y] == 'e') {ans++;	//節(jié)點(diǎn)為終點(diǎn)，所以找到一條走到終點(diǎn)的路，ans++；return ;}if (check_in(x, y) && pos[x][y] != '#' && !trace[x][y]) {   //如果這個節(jié)點(diǎn)不是終點(diǎn)且沒越界，不是墻且沒走過，則統(tǒng)計四周情況trace[x][y] = 1;for (int i = 0; i < 4; i++) {int xx = x + dir[i][0];int yy = y + dir[i][1];dfs(xx, yy);}trace[x][y] = 0;		//清空路線，找下一條路}
}int main() {cin >> n >> m;int x, y;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> pos[i][j];if (pos[i][j] == 's') {x = i, y = j;}}}dfs(x, y);cout << ans << endl;return 0;
}

4. 最大的蛋糕塊

4.1 題干信息

① 背景說明概述

這一天蒜頭君生日，他的朋友們一起來給蒜頭君買一個大的蛋糕過生日。游戲做完后到了切蛋糕的時刻了，朋友們知道蒜頭君喜歡吃蛋糕，便讓蒜頭君自己給自己切-塊最大的。蒜頭君看朋友們這么熱情也就不客氣了。

② 問題描述

• 這塊蛋糕是由R*C的網(wǎng)格構(gòu)成，每個網(wǎng)格上面都放有不同的水果。蒜頭君把這些水果分為兩類，一類是自己喜歡吃的水果，用'#'來表示;一類是自己不喜歡吃的水果，用'.'來表示。
• 蒜頭君對切出的蛋糕有如下要求:
  • 切出的蛋糕連成一塊(可以不為矩形，但必須在網(wǎng)格上連通)
  • 切出的蛋糕只包含自己喜歡吃的水果
• 請問，蒜頭君最大可以吃到多大的蛋糕?

③ 輸入格式

• 第一行輸入兩個被空格隔開的整數(shù)R(1≤R≤1000)和C(1≤C≤1000)。然后會有一個R*C的網(wǎng)格，由'#'和'.'組成。

④ 輸出格式

• 輸出一個整數(shù)，表示蒜頭君可以吃到的蛋糕最大是多少(即對應(yīng)到網(wǎng)格中的格子數(shù))。

⑤ 樣例輸入

5 6
.#....
..#...
..#..#
...##.
.#....

⑥ 樣例輸出

2

4.2 思路解釋

和題2《踏青》的總體思路一樣，但《踏青》求的是帶'#'每部分的數(shù)量，而本題是求每部分里'#'最多的數(shù)量。所以這道題只需要在統(tǒng)計每部分時記錄'#'的數(shù)量再進(jìn)行比較即可。

4.3 code展示

#include<iostream>
#include<stdio.h>
using namespace std;int r, c, ans = 0, cnt = 0;
char pos[105][105];
bool trace[105][105];
int dir[4][2] = { {-1, 0},{0,-1},{1,0},{0,1} };bool check_in(int x, int y) {return (x >= 1 && x <= r && y >= 1 && y <= c);
}void dfs(int x, int y) {if (!check_in(x, y) || pos[x][y] != '#' || trace[x][y]) {	//深搜過程中不合要求的返回;return;}trace[x][y] = 1; //標(biāo)記訪問過cnt++; //記錄數(shù)量for (int i = 0; i < r; i++) {int xx = x + dir[i][0];int yy = y + dir[i][1];if (pos[xx][yy] == '#') {dfs(xx, yy);}}
}int main() {cin >> r >> c;int x, y;for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {cin >> pos[i][j];}}for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {if (!trace[i][j] && pos[i][j] == '#') {	//如果是'#'，且之前沒被訪問過，則用dfs記錄下cnt = 0;		//需要將該位置能求到的數(shù)量重置為0dfs(i, j);	//用dfs求一下所有‘#’的數(shù)量if (ans < cnt) {ans = cnt;	//更新一下ans}}}}cout << ans << endl;return 0;
}

5. 家譜

5.1 題干信息

① 背景說明概述

家譜，又稱族譜、宗譜等，是一種以表譜形式，記載一個家族的世系繁衍及重要人物事跡的書?；实鄣募易V稱玉牒，如新朝玉牒、皇宋玉牒。它以記載父系家族世系、人物為中心，由正史中的帝王本紀(jì)及王侯列傳、年表等演變而來。家譜是一種特殊的文獻(xiàn)，就其內(nèi)容而言，是中國五千年文明史中具有平民特色的文獻(xiàn)，記載的是同宗共祖血緣集團(tuán)世系人物和事跡等方面情況的歷史圖籍。家譜屬珍貴的人文資料，對于歷史學(xué)、民俗學(xué)、人口學(xué)、社會學(xué)和經(jīng)濟(jì)學(xué)的深入研究，均有其不可替代的獨(dú)特功能。

② 問題描述

• 這一天蒜頭君拿到了自己家的家譜，蒜頭君便想知道，在自己家的家譜中，每位祖先有多少直系后代(直系后代包括他的孩子和他孩子的直系后代)。但是家族歷史源遠(yuǎn)流長，家譜實(shí)在太龐大了，自己一個人完全數(shù)不過來。熱心的你便自告奮勇幫蒜頭君寫一個程序，來統(tǒng)計每位祖先有多少直系后代。

③ 輸入格式

• 輸入的第一行有一個整數(shù)n(1<n≤100000)，表示家譜中的總?cè)藬?shù)。接下來讀入n- 1行，每行有兩個整數(shù)x(1≤x≤n),y(1≤y≤n),表示x是y的父母。

④ 輸出格式

• 輸出n行，每行有一個整數(shù)，表示第i個人有多少個直系后代。

⑤ 樣例輸入

4
1 2
1 3
2 4

⑥ 樣例輸出

3
1
0
0

5.2 思路解釋

本題輸入數(shù)值的大小不確定，所以如果指定數(shù)組大小，則可能報錯，所以我們采用動態(tài)數(shù)組vector來統(tǒng)計son數(shù)量。所以首先，我們先找根節(jié)點(diǎn)，所以要找直系兒子，則需要把所有兒子的后代標(biāo)記一下，最后未被標(biāo)記的就是直系兒子。我們找到根節(jié)點(diǎn)，需要先對根節(jié)點(diǎn)的后代進(jìn)行搜索，直到找到答案。

5.3 code展示

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int N = 1e5 + 10;int n, x, y, u;
vector<int> son[N];	//使用動態(tài)數(shù)組，便于插入和刪除
bool judge_son[N];	//判斷是否是兒子
int ans[N];int dfs(int a) {	//	找有多少個直系后代【不包括自己】，但統(tǒng)計時為了方便，則統(tǒng)計自己int cnt = 0;int len = son[a].size();for (int i = 0; i < len; i++) {	//首先，找根節(jié)點(diǎn)的后代cnt += dfs(son[a].at(i));	//找根節(jié)點(diǎn)的直接后代，或者寫dfs(son[u][i])}ans[u] = cnt;	//統(tǒng)計后代個數(shù)return cnt + 1; //加上自己
}int main() {cin >> n;for (int i = 1; i < n; i++) {cin >> x >> y; //輸入x,y 表示x是y的父親son[x].push_back(y); //將y放入son[x]的動態(tài)數(shù)組中judge_son[y] = true; //y已經(jīng)作為兒子了，所以標(biāo)為true;}for (int i = 1; i <= n; i++) {	//找起始位置，即找“根”節(jié)點(diǎn)if (!judge_son[i]) {	//找到賦給u,并breaku = i;break;}}dfs(u);for (int i = 1; i <= n; i++) {cout << ans[i] << endl;}return 0;
}

最后，感謝大家支持u （^ _ ^）

如果感覺這篇文章對你有幫助的話，不妨三連支持下，十分感謝(?ω?)。

printf("點(diǎn)個贊吧*^*");

cout << "收藏一下叭o_o";

System.out.println("評論一下吧^_^");

print("關(guān)注一下叭0-0")