搜索就是通过不停的试探去寻找一种解法。基础:暴力搜索法,深搜和广搜三种
高级的有IDDFS,DBFS,A,IDA等等,本蒻今天讲DFS && BFS。

DFS

算法过程 DFS(状态 A)

1.判断当前状态是否合法。合法则继续执行,否则回到上一次调用。

2.调用DFS(状态A+t) 即先走下一层。

习题1

CCPC2019哈尔滨站

题面描述

六个字符串,从每个字符串中取出一个字符,问能否构成”harbin”?如果能构
则输出”Yes”,否则输出”No”。

输入描述

多组测试,第一个数字 T 代表测试组数
每组测试输入6个字符串
所有字符串长度之和不超过 2e6

输出描述

每组测试输出”Yes”或”No”。

AC代码

#include <bits/stdc++.h>
using namespace std;
char s[2002000];
bool mp[7][7];
bool a[7];
bool dfs(int p)
{
    if(p == 7) return true;
    for(int i = 1; i <= 6; ++i)
    {
        if(mp[p][i] && a[i])
        {
            a[i] = 0;
            if(dfs(p + 1)) return true;
            a[i] = 1;
        }
    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(mp,0,sizeof(mp));
        memset(a,1,sizeof(a));
        for(int i = 1; i <= 6; ++i)
        {
            scanf("%s",s);
            int len = strlen(s);
            for(int j = 0; j < len; ++j)
                if(s[j] == 'h') mp[i][1] = 1;
                else if(s[j] == 'a') mp[i][2] = 1;
                else if(s[j] == 'r') mp[i][3] = 1;
                else if(s[j] == 'b') mp[i][4] = 1;
                else if(s[j] == 'i') mp[i][5] = 1;
                else if(s[j] == 'n') mp[i][6] = 1;
        }
        if(dfs(1)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

习题2

题面描述(简单版本)

有一个 n行m列 的网格,每个格子里非 0 即 1,有 q 次操作,每次
给定一个以(x1,y1)为左上角,(x2,y2)为右下角的矩形内所有格子里
的数字都变成1。问每次操作之后,所有数字为 1 的格子构成的四连通
块的个数。

输入描述

输入第一行两个整数 n,m(1 <= n,m <= 300),表示网格的大小。
接下来 n 行,每行一个长为 m 的 01串,表示初始网格大小。
接下来一行一个整数 q, 表示操作个数。
接下来 q 行,每行四个整数 x1, y1, x2, y2(1<=x1<=x2<=n,1<=y1<=y2<=m)
表示把以(x1,y1)为左上角,(x2,y2)为右下角的矩形中的元素都变为1。

输出描述

输出共 q 行,每行一个整数,表示每次操作后含有数字1的格子构成的四连通块个数

样例输入

5 6
101010
000001
101010
000001
101010
3
1 2 5 2
4 4 4 4
1 3 3 6

样例输出

6
7
2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 350;
char mp[maxn][maxn],flag[maxn][maxn];
int head[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int n, m ,q, ans;

bool inbound(int x, int y)
{
    if(x>=1 && x <= n && y>=1 && y<=m)
        return true;
    return false;
}

void dfs(int x,int y)
{
    mp[x][y] = '0';
    for(int i = 0; i < 4; i++)
    {
        int dx = x + head[i][0];
        int dy = y + head[i][1];
        if(mp[dx][dy]=='1' && inbound(dx,dy))
        {
            mp[dx][dy] = '0';
            dfs(dx,dy);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>mp[i][j];
    cin>>q;
    while(q--)
    {
        ans = 0;
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        for(int i = x1; i <= x2; i++)
            for(int j = y1; j <= y2; j++)
                mp[i][j] = '1';

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                flag[i][j]=mp[i][j];

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(mp[i][j] == '1')
                {
                    ans++;
                    dfs(i,j);
                }
            }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                mp[i][j]=flag[i][j];
        printf("%d\n",ans);
    }
    return 0;
}

BFS

算法过程(广度优先搜索)

1.一层一层的走

2.广搜总是每次都把离上一状态最近的状态用一个队列记录下来

3.记录之后,检查队列是否为空,如果不为空,就将队列元素弹出,并

且以这个状态为”根节点”进行广度优先搜索。

4.直到整个队列为空。

习题三 走迷宫(Bfs)

题面描述

一个 n行 m 列的迷宫,迷宫的格子里分别放 0 和 1,1 表示可以通过,0表
示不可以通过。
从某个点开始,有四个方向可以走,前进方格中的数字为 1 时表示可以通过,
0表示不可通过,要另找路径。
起点是左上角,输入终点坐标,给出最短路径。

输入

6 5 6 5
1 0 0 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1

输出

17
(11)(21)->(22)->(23)->(24)->(25)->(35)->(45)->(44)->(43)->(42)->(41)->(51)->(61)->(62)->(63)->(64)->(65)->

#include <bits/stdc++.h>
using namespace std;
int n,m,tx,ty;
int mp[110][110];
int qu[10010];  //模拟队列,存所有的点
int l,r;    //[l,r)
int dis[110][110];  //dis[][]表示这个点是否被访问过
int pre[10010];  //pre[]记录方案
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
bool inbound(int x, int l, int r)
{
    if(x < l || x >= r)
        return false;
    return true;
}

void write(int s,int x)
{
    if(s == x)
    {
        printf("(%d%d)",s/m+1,s%m+1);
        return ;
    }
    write(s,pre[x]);
    printf("(%d%d)->",x/m+1,x%m+1);
}

void bfs(int s, int t)
{
    memset(dis,-1,sizeof(dis));
    memset(qu,0,sizeof(qu));
    l = 0; r = 0;
    qu[0] = s;  //起点存入队列
    r++;   //保证区间左闭右开
    dis[s/m][s%m] = 0;
    while(l < r)
    {
        int point = qu[l];  //取出队首元素
        if(point == t) break;   //到达终点,提前退出
        l++;  //出队
        int x = point/m, y = point%m;  //点的位置
        for(int i = 0; i < 4; i++)   //四个方向扩展
        {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if(!inbound(tx,0,n)||!inbound(ty,0,m))
                continue;
            if(dis[tx][ty] == -1 && mp[tx][ty] == 1)
            {
                dis[tx][ty] = dis[x][y] + 1;  //(x,y)-->(tx,ty)
                pre[tx*m+ty] = point; //记录前驱
                qu[r] = tx*m+ty;  //放入队列
                r++;   //进队
            }
        }
    }
    printf("%d\n",dis[t/m][t%m]);
    write(s,t);
}

int main()
{
    scanf("%d%d", &n,&m);
    scanf(" %d%d", &tx,&ty);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf(" %d", &mp[i][j]);
    tx--;ty--;
    bfs(0 ,tx*m+ty);
    return 0;
}

总结

搜索解决问题:
在一个空间中寻找目标
空间指的是解空间
目标是指目标状态
解空间:如果把一个问题的抽象成一个数学上的向量,那么包含这个向量
空间,也就是解空间。
状态:用于描述问题或问题解的一些向量。


一个爱折腾且喜欢研究算法的大学生