搜索的题型

一.dfs

1. **地图类问题** 

### 连通块问题：
遍历每一个点，对每一个点（未标记过的）进行搜索，每搜索一次连通块数+1，dfs部分不需要回溯

#include<bits/stdc++.h>//用连通块问题法二
using namespace std;
int n,m,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int a[505][505],ans;
bool st[505][505];//注意这道题找的是未淹没的块和全球变暖那道题很像
//1.初始化地图为数字地图
//2.看清楚边界从外面开始还是地图里面开始
//3.搜索部分 对于越界部分和障碍回溯并将地图该点修改表示已经搜过
//4.最后未被标记的即为未淹没的连通块
bool check(int x,int y)
{
    return x>=0&&x<=n+1&&y>=0&&y<=m+1;//注意将地图扩展一圈
}
void dfs(int x,int y)
{
    if(!check(x,y)||a[x][y])return;//遇到障碍不去搜
    a[x][y]=2;//表示搜过了
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        dfs(nx,ny);//这里不必处理越界而是向下搜的时候处理了越界问题
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            if(c=='0')a[i][j]=0;
            else a[i][j]=1;
        }
    }
    dfs(0,0);//地图外开始搜索
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!a[i][j])ans++;
        }
    }
    cout<<ans;
}  

### 2.棋盘类问题
    思路：1.dfs先确定好参数，终止条件，搜索树
          2.这道题明显 x,y,u(行，列，棋子数目)
          3.当棋子数目==n时终止，一行一行搜索，当列到终点换行搜并终止
            当行到终点则终止
          4.搜索树则是该点放棋子还是不放棋子，用bool 数组存一下棋盘状态
          5.检查部分，就是对行 列 对角线 统计五子连线个数，最终ans记录第一次出现的个数

例题： https://www.luogu.com.cn/problem/P1479

#include<bits/stdc++.h>
using namespace std;
int n,ans,k;//模拟棋盘一行一行搜索
bool st[10][10],vis[30];
void check()
{
    k=0;
    for(int i=0;i<5;i++)
    {
        if(st[i][0]&&st[i][1]&&st[i][2]&&st[i][3]&&st[i][4])k++;//行
        if(st[0][i]&&st[1][i]&&st[2][i]&&st[3][i]&&st[4][i])k++;//列
    }
    //对角线
    if(st[0][0]&&st[1][1]&&st[2][2]&&st[3][3]&&st[4][4])k++;
    if(st[0][4]&&st[1][3]&&st[2][2]&&st[3][1]&&st[4][0])k++;
    if(!vis[k])vis[k]=1,ans+=k;
}
void dfs(int x,int y,int u)
{
    if(u==n)
    {
        check();
        return;
    }
    if(x==5)return;
    if(y==5)
    {
    dfs(x+1,0,u);
    return; 
    }
    st[x][y]=1;
    dfs(x,y+1,u+1);//放棋
    st[x][y]=0;
    dfs(x,y+1,u);//不放棋子
}
int main()
{
    cin>>n;//5*5每个位置放或者不放
    dfs(0,0,0);
    cout<<ans;
    return 0;
}