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;
}