DFS 深度優化搜索
DFS 演算法
思想：一直往深處走，直到找到解或者走不下去為止
類似于樹的先根遍歷，就是不撞南墻不回頭
模板一：
DFS(dep,..)//dep代表目前DFS的深度
{
if(找到解||走不下去)
{
...
return;
}
DFS(dep+1,..)//列舉下一種情況
}
模板二：
DFS(dep,..)
{
if(判斷條件)
return;
for(擴展轉態)
{
判斷合法；
記錄；
DFS(dep+1,...)
回溯；
}
}
DFS遍歷圖
1.從圖中v0出發，訪問v0，
2.找出v0的第一個未被訪問的鄰接點，訪問該頂點，以該頂點為新頂點，重復此步驟，直至剛訪問過的頂點沒有未被訪問的鄰接點為止，
3.回傳前一個訪問過的仍有未被訪問鄰接點的頂點，繼續訪問該頂點的下一個未被訪問領接點，
4.重復2,3步驟，直至所有頂點均被訪問，搜索結束，
v0->v2->v4->v6->v1->v5->v3
DFS 題型
一：資料型
Prime Ring Problem
題意
已知一個數n，將數字1~n圍成一個圓環，要求： 相鄰兩個數之和為素數，
0<n<20
輸出：
- 數字的方向一致（同順時針或同逆時針），并保證排列不重復
- 只有一個數（n==1）時，輸出1
- 輸出Case k:（k為資料組數），每一組輸出（第一個除外）之前都有一個空行
思路
每次遞回前判斷前兩個數之和是否為素數，因為是環，最后一個數和第一個數也要滿足
DFS前可以先用素數篩，求50內的素數，n最大20,最大的兩個素數和<50
代碼
#include<bits/stdc++.h>
using namespace std;
const int MAX=50;
int prime[25];//素數陣列
bool vis[25]; //訪問陣列
int n;// 個數
int ans[MAX];//解答輸出陣列
void Prime_set() //篩法求素數
{
//Isprime 0、 IsNotprime 1
for(int i = 2; i<=sqrt(MAX) ;++ i)
if(prime[i] == 0)
{
for(int j = 2;i*j<=MAX;++j)
prime[i*j] = 1;
}
prime[1] = 0,vis[1]=true;//1雖然不是素數，但在此假設為0，將vis[1]設為true即不會遍歷到1
}
void DFS(int depth)
{
if(prime[ans[depth-1]+ans[depth-2]]!=0) return ; //前兩個數之和不是素數退出
if(depth==n+1&&prime[ans[depth-1]+ans[1]]!=0) return ; //當選到最后一個數時，第一個數和最后一個數之和不是素數時退出
if(depth==n+1) //選到最后一個數，輸出
{
for(int i=1;i<=n;i++)
{
if(i==1) cout<<ans[i];
else cout<<" "<<ans[i];
}
cout<<endl;
}
for(int i=2;i<=n;i++) //把1~n按照一定順序（DFS求得）填入陣列ans
{
if(!vis[i])
{
vis[i]=true;
ans[depth]=i;
DFS(depth+1);
vis[i]=false;
}
}
}
int main(){
int t=1;
Prime_set();
while(cin>>n)
{
cout<<"Case "<<t++<<":"<<endl;
memset(vis,false,sizeof(vis));
memset(ans,0,sizeof(ans));
ans[1] = 1;//1永遠是首元素
if(n==1) cout<<"1"<<endl;
else
DFS(2);//1永遠是首元素，從2開始DFS ；也防止之后depth-2<0
cout<<endl;
}
return 0;
}
題目描述：選數
已知 n個整數 x1,x2,…,x n x_nx**n 以及1個整數k(k<n)，從n個整數中任選k個整數相加，可分別得到一系列的和，例如當n=4,k=3,4個整數分別為3,7,12,19時，可得全部的組合與它們的和為：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
現在，要求你計算出和為素數共有多少種，
例如上例，只有一種的和為素數：3+7+19=29
#include<bits/stdc++.h>
using namespace std;
int a[10005],sum=0,ans=0;
int n,k;
int sushu(int f)
{
for(int i=2;i*i<=f;i++)
{
if(f%i==0)
return 0;
}
return 1;
}
void dfs(int x,int y)//x表示差幾個數，y表示選到a[y]
{
if(x==0)
ans+=sushu(sum);
else
{
y++;
for(int i=y;i<=n;i++)
{
sum+=a[i];
x--;
dfs(x,i);
sum-=a[i];//回溯
++x;
}
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(k,0);
cout<<ans<<endl;
getchar();
getchar();
return 0;
}
二：圖型
矩陣中的路徑
請設計一個函式，用來判斷在一個矩陣中是否存在一條包含某字串所有字符的路徑，
路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子，
如果一條路徑經過了矩陣中的某一個格子，則之后不能再次進入這個格子，
注意：
樣例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]
str="BCCE" , return "true"
str="ASAE" , return "false"
CODE:
class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string &str)
{
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[i].size();j++)
{
if(dfs(matrix,str,0,i,j))//對每一個點深搜，起點不一樣
return true;
}
}
return false;
}
bool dfs (vector<vector<char>>& matrix,string &str,int u,int i,int j )
{
if(matrix[i][j]!=str[u])return false;//不滿足
if(u==str.size()-1)return true;//找到了一條路徑滿足
char t=matrix[i][j];//回溯需要
matrix[i][j]='*';
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};//方向向量
for(int m=0;m<4;m++)
{
int a=i+dx[m],b=j+dy[m];
if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size())
{
if(dfs(matrix,str,u+1,a,b))
return true;
}
}
matrix[i][j]=t;//回溯
return false;
}
};
走出迷宮
小明現在在玩一個游戲,迷宮是一個N*M的矩陣，
小明的起點在地圖中用“S”來表示，終點用“E”來表示，障礙物用“#”來表示，空地用“.”來表示，
障礙物不能通過，小明如果現在在點（x，y）處，那么下一步只能走到相鄰的四個格子中的某一個：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；
小明想要知道，現在他能否從起點走到終點
樣例輸入
3 3
S..
..E
...
3 3
S##
###
##E
樣例輸出
Yes
No
AC代碼
#include<bits/stdc++.h>
using namespace std;
int n,m,flag=0,a,b;//flag是標記能否到達
const int MAX=510;
char s[MAX][MAX];
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};//方向向量
void DFS(int i,int j)
{
if(flag||s[i][j]=='#'||i<0||i>=n||j<0||j>=m)//判出
return;
if(s[i][j]=='E')//到達終點
{
flag=1;
return;
}
s[i][j]='#';//走過了的路不回頭
for(int e=0; e<4; e++)
DFS(i+dx[e], j+dy[e]);//繼續深搜
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
flag=0;//每一組資料重新賦值為0
for(int i=0;i<n;i++)
scanf("%s",s[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(s[i][j]=='S')a=i,b=j;//起點標記
DFS(a,b);
if(flag)
puts("Yes");
else
puts("No");
}
return 0;
}
