深度優(yōu)先搜索（DFS）
深度優(yōu)先搜索俘侠，重點(diǎn)就在于“深度”一詞，不碰到死胡同就不回頭种玛。
深度優(yōu)先搜索是一種枚舉所有完整路徑以遍歷所有情況的搜索方法曹洽。
整個(gè)過程和出棧入棧的過程極為相似，可以使用棧來實(shí)現(xiàn)蹭沛。
首先先對問題進(jìn)行分析臂寝，得到岔路口和死胡同章鲤；再定義一個(gè)棧，以深度為關(guān)鍵詞訪問這些岔道口和死胡同咆贬，并將它們?nèi)霔０芑玻欢?dāng)離開這些岔道口和死胡同時(shí)，將它們出棧素征。
使用遞歸可以很好地實(shí)現(xiàn)深度優(yōu)先搜索集嵌。只能說遞歸是深度優(yōu)先搜索的一種實(shí)現(xiàn)方式。在使用遞歸時(shí)御毅，系統(tǒng)會調(diào)用一個(gè)叫系統(tǒng)棧的東西來存放遞歸中每一層的狀態(tài)根欧，因此使用遞歸來實(shí)現(xiàn)DFS的本質(zhì)其實(shí)還是棧。
注意端蛆，當(dāng)DFS復(fù)雜度過高凤粗，或數(shù)據(jù)極端的情況，必要的時(shí)候需用到剪枝今豆。
關(guān)于dfs參數(shù)問題嫌拣，什么在變化，就把什么設(shè)置成參數(shù)呆躲。
DFS模板
void dfs() { //參數(shù)用來表示狀態(tài)
if(到達(dá)終點(diǎn)狀態(tài)) {
...//根據(jù)題意添加
return;
}
if(越界或者是不合法狀態(tài))
return;
if(特殊狀態(tài))//剪枝
return ;
for(擴(kuò)展方式) {
if(擴(kuò)展方式所達(dá)到狀態(tài)合法) {
修改操作;//根據(jù)題意來添加
標(biāo)記异逐；
dfs（）；
(還原標(biāo)記)插掂；
//是否還原標(biāo)記根據(jù)題意
//如果加上（還原標(biāo)記）就是 回溯法
}
}
}
實(shí)例1（全排列加素?cái)?shù)）：
已知 n 個(gè)整數(shù)b1,b2,…,bn
以及一個(gè)整數(shù) k（k＜n）灰瞻。
從 n 個(gè)整數(shù)中任選 k 個(gè)整數(shù)相加，可分別得到一系列的和辅甥。
例如當(dāng) n=4酝润，k＝3，4 個(gè)整數(shù)分別為 3璃弄，7要销，12，19 時(shí)夏块，可得全部的組合與它們的和為：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34疏咐。
現(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種,并給出每種組合的和脐供。
例如上例凳鬓，只有一種的和為素?cái)?shù)：3＋7＋19＝29。
輸入
第一行兩個(gè)整數(shù)：n , k （1<=n<=20患民，k＜n）
第二行n個(gè)整數(shù)：x1,x2缩举，…,xn （1<=xi<=5000000）
輸出
一個(gè)整數(shù)（滿足條件的方案數(shù)）。
樣例輸入
4 3
3 7 12 19
樣例輸出
1
29
#include<bits/stdc++.h>
using namespace std;
int sum = 0;
int n, k;
int a[105];
int p[105];
bool vis[105];
vector<int> ans;
bool isprime(int sum) {
if(sum <= 1) return false;
for(int i = 2; i * i <= sum ; i++) {
if(sum % i == 0) {
return false;
}
}
return true;
}
void dfs(int index) {
if(index == k + 1 ) {
if(isprime(sum)) {
ans.push_back(sum);
}
return;
}
for(int i = 1; i <= n; i++) {
if(vis[i] == false && i > p[index - 1]) { //按序排列 剪枝
p[index] = i;
vis[i] = true;
sum += a[i];
dfs(index + 1);
vis[i] = false;
sum -= a[i];
}
}
}
int main() {
memset(vis, 0, sizeof(vis));
cin>> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = i;
}
dfs(1);
cout << ans.size() << endl;
for(vector<int>::iterator it = ans.begin();it != ans.end(); it++) {
printf("%d\n", *it);
}
return 0;
}
廣度優(yōu)先搜索（BFS）
Breadth First Search , BFS， 以廣度為第一關(guān)鍵詞仅孩。
當(dāng)碰到岔道口時(shí)托猩，總是先依次訪問從該岔道口能直接到達(dá)的所有結(jié)點(diǎn)，然后再按這些結(jié)點(diǎn)被訪問的順序去依次訪問它們能直接到達(dá)的所有結(jié)點(diǎn)辽慕，依次類推京腥，直到所有結(jié)點(diǎn)都被訪問為止。
BFS模板
void BFS(int s) {
queue<int> q;
q.push(s);
while(!q.empty()) {
node top = q.front();
//取出隊(duì)首元素top;
...
//訪問隊(duì)首元素top操作;
q.pop();BFD
//將隊(duì)首元素出隊(duì);
將top的下一層結(jié)點(diǎn)中未曾入隊(duì)的結(jié)點(diǎn)全部入隊(duì)溅蛉，并設(shè)置為已入隊(duì);
}
}
實(shí)現(xiàn)步驟：
- 定義隊(duì)列q公浪，并將起點(diǎn)s入隊(duì)
- 寫一個(gè)while循環(huán)，循環(huán)條件是隊(duì)列是q非空
- 在while循環(huán)中船侧，先取出隊(duì)首元素top欠气，然后訪問它（訪問可以是任何事情，例如將其輸出）镜撩。訪問完將其出隊(duì)预柒。
- 將top的下一層結(jié)點(diǎn)中所有未曾入隊(duì)的結(jié)點(diǎn)入隊(duì)，并標(biāo)記它們的層號為now的層號加1袁梗，同時(shí)設(shè)置這些入隊(duì)的結(jié)點(diǎn)已入過隊(duì)宜鸯。
- 返回步驟2繼續(xù)循環(huán)
實(shí)例2：
給出一個(gè)m×n的矩陣，矩陣中的元素為0或1遮怜。稱位置(x, y)與其上下左右四個(gè)位置(x, y+1)淋袖、(x, y-1)、(x+1,y)锯梁、(x-1,y)是相鄰的即碗。如果矩陣中有若干個(gè)1是相鄰的（不必兩兩相鄰），那么稱這些1構(gòu)成了一個(gè)“塊"涝桅。求給定的矩陣中”塊“的個(gè)數(shù)
樣例輸入
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
樣例輸出
4
代碼
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 100;
struct node {
int x, y; //位置(x, y)
} Node;
int n, m; //矩陣大小為n*m
int matrix[maxn][maxn]; //01矩陣
bool inq[maxn][maxn] = {false}; //記錄位置(x, y)是否已入過隊(duì)
int X[4] = {0, 0, 1, -1}; //增量數(shù)組
int Y[4] = {1, -1, 0, 0};
bool judge(int x, int y) { //判斷坐標(biāo)(x, y)是否需要訪問
//越界返回false
if(x >= n || x < 0 || y >= m || y < 0) return false;
//不滿足條件返回false
if(matrix[x][y] == 0 || inq[x][y] == true) return false;
return true;
}
//BFS函數(shù)訪問位置(x, y)所在的塊拜姿，將該塊中所有"1"的inq都設(shè)置為true
void BFS(int x, int y) {
queue<node> Q; //定義隊(duì)列
Node.x = x, Node.y = y; //當(dāng)前結(jié)點(diǎn)坐標(biāo)為(x, y)
Q.push(Node); //將結(jié)點(diǎn)Node入隊(duì)
inq[x][y] = true; //設(shè)置(x, y)已入過隊(duì)
while(!Q.empty()) {
node top = Q.front(); //取出隊(duì)首元素
Q.pop(); //隊(duì)首元素出隊(duì)
for(int i = 0; i < 4; i++) { //循環(huán)四次烙样，得到四個(gè)相鄰位置
int newX = top.x + X[i];
int newY = top.y + Y[i];
if(judge(newX, newY)) { //如果新位置(newX, newY)需要訪問
//設(shè)置Node的坐標(biāo)為(newX, newY)
Node.x = newX, Node.y = newY;
Q.push(Node); //將結(jié)點(diǎn)Node加入隊(duì)列
inq[newX][newY] = true; //設(shè)置位置(newX, newY)已入過隊(duì)
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int x = 0; x < n; x++) {
for(int y = 0; y < m; y++) {
scanf("%d", &matrix[x][y]);
}
}
int ans = 0; //存放塊數(shù)
for(int x = 0; x < n; x++) { //枚舉每一個(gè)位置
for(int y = 0; y < m; y++) {
//如果元素為1冯遂， 且未入過隊(duì)
if(matrix[x][y] == 1 && inq[x][y] == false) {
ans++; //塊數(shù)+1
BFS(x, y); //訪問整個(gè)塊，將該塊所有"1"的inq都標(biāo)記未true
}
}
}
printf("%d\n", ans);
return 0;
}
實(shí)例3：
給定一個(gè)nm大小的迷宮谒获，其中代表不可通過的墻壁蛤肌，而”.”代表平地，S表示起點(diǎn)批狱，T代表終點(diǎn)裸准。移動(dòng)過程中，如果當(dāng)前位置是(x, y)(下標(biāo)從0開始)赔硫，且每次只能前往上下左右(x, y+1)炒俱、(x, y-1)、(x+1, y)、(x-1, y)四個(gè)位置的平地权悟，求從起點(diǎn)S到達(dá)終點(diǎn)T的最少步數(shù)砸王。
樣例輸入
5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3
樣例輸出
11
代碼
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 100;
struct node {
int x, y; //位置(x, y)
int step; //step為從起點(diǎn)S到達(dá)該位置的最少步數(shù)（即層數(shù)）
}S, T, Node; //S為起點(diǎn)，T為終點(diǎn)峦阁，Node為臨時(shí)終點(diǎn)
int n, m; //n為行谦铃，m為列
char maze[maxn][maxn]; //迷宮信息
bool inq[maxn][maxn] = {false}; //記錄位置(x, y)是否已入過隊(duì)
int X[4] = {0, 0, 1, -1}; //增量數(shù)組
int Y[4] = {1, -1, 0, 0};
//檢測位置(x, y)是否有效
bool test(int x, int y) {
if(x >= n || x < 0 || y >= m || y < 0) return false; //超過邊界
if(maze[x][y] == '*') return false; //墻壁*
if(inq[x][y] == true) return false; //已入過隊(duì)
return true; //有效位置
}
int BFS() {
queue<node> q; //定義隊(duì)列
q.push(S); //將起點(diǎn)S入隊(duì)
while(!q.empty()) {
node top = q.front(); //取出隊(duì)首元素
q.pop(); //隊(duì)首元素出隊(duì)
if(top.x == T.x && top.y ==T.y) {
return top.step;
}
for(int i = 0; i < 4; i++) { //循環(huán)4次，得到4個(gè)相鄰位置
int newX = top.x + X[i];
int newY = top.y + Y[i];
if(test(newX, newY)) {
//設(shè)置Node的坐標(biāo)為(newX, newY)
Node.x = newX;
Node.y = newY;
Node.step = top.step + 1; //Node層數(shù)為top的層數(shù)加1
q.push(Node); //將結(jié)點(diǎn)Node加入隊(duì)列
inq[newX][newY] = true; //設(shè)置位置(newX, newY)已入過隊(duì)
}
}
}
return -1; //無法到達(dá)終點(diǎn)T時(shí)返回-1
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) {
getchar(); //過濾掉每行后面的換行符
for(int j = 0; j < m; j++) {
maze[i][j] = getchar();
}
maze[i][m + 1] = '\0';
}
scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y); //起點(diǎn)和終點(diǎn)的坐標(biāo)
S.step = 0; //初始化起點(diǎn)的層數(shù)為0榔昔， 即S到S的最少步數(shù)為0
printf("%d\n", BFS());
return 0;
}
