2022-10-15 深搜

深度优先搜索

深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。 属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

 深搜的模板：

void dfs(int x,int y)
{
    if(搜索要满足的条件){相应的操作;return; }
    for(循环搜索的方向，即探寻下一步)
    {    根据当前的x,y得到下一步的坐标tx,ty
        if(对tx,ty做越界判断)continue;
        if(当前坐标vis[tx][ty]==0 && 下一步在地图上是可走的)
        {    vis[tx][ty] = 1;
            更新相应数据，如求和、步长等等
            dfs(tx,ty); 以tx,ty作为新的起点传入dfs中去寻找符合条件的下一步
            vis[tx][ty] = 0;
            将更新的数据回溯到未更新前，如步长-1，求和--等 
        }
    }
}

TZOJ 3286: Lake Counting

#include<bits/stdc++.h>
using namespace std;
char ma[1005][1005]; //地图 
int vis[1005][1005]; //标记数组，标记某点坐标是否已访问过 
int nex[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},{1,1},{1,-1},{-1,-1}}; //方向数组，表面搜索下一步的方向，这里为右下左上 
int n,m;
void dfs(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int tx = x+nex[i][0]; //下一步坐标tx = 当前坐标x+第i个方向的第0个数nex[i][0]
        int ty = y+nex[i][1];
        if(tx<1||tx>n||ty<1||ty>m)continue; //越界判断
        if(ma[tx][ty]=='W' && vis[tx][ty]==0)//如果第(tx,ty)个点是湖泊W，且在vis上没访问过
        {
            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>>ma[i][j];
        
            
    //以上是输入
    int ans = 0; //湖泊数
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(ma[i][j]=='W' && vis[i][j]==0) //如果第(i,j)个点是湖泊W，且在vis上没访问过
            {
                vis[i][j] = 1; //访问
                ans++; //湖泊数+1
                dfs(i,j);//将i,j相邻的所有湖泊搜索标记 
            } 
        } 
    cout<<ans;
     return 0;
}

TZOJ 4833: 选数

#include<bits/stdc++.h>
using namespace std;
int ma[105]; //地图 
int vis[105]; //标记数组，标记某点坐标是否已访问过 
int n,k,sum,ans,len;
void dfs(int x);
int prime(int n);
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>ma[i];
    //以上是输入
    dfs(1); //从0开始 
    cout<<ans;
     return 0;
}
void dfs(int x)
{
    if(len==k){
        if(prime(sum))ans++;
        return;
    }
    for(int i=x;i<=n;i++)
    {
        if(vis[i]==0)
        {
            sum+=ma[i];
            len++;
            vis[i] = 1;
            dfs(i+1);
            len--;
            vis[i] = 0;
            sum-=ma[i];
        }
    }
}
int prime(int n)
{
    if(n==1)return 0;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)return 0;
    return 1;
}