c++ 算法之搜索

搜索是 c++ 之中一个简单而重要的算法，每一个 OIer 必备的基础算法，你知道它究竟是什么吗？

zhhg0123

3730人浏览 · 2024-04-01 18:49:02

zhhg0123 · 2024-04-01 18:49:02 发布

搜索是 c++ 之中一个简单而重要的算法，每一个 OIer 必备的基础算法，你知道它究竟是什么吗？

一、深度优先搜索

1.简介

深度优先搜索（简称“深搜”）是通过递归实现的，当搜索到一个元素时。如果这是最后一个元素，就退出递归，统计个数或输出路径。如果不是最后一个元素，就搜索他的下一个元素。由于在循环中直接就进入了下一层递归，所以它是先找一条路，找到头，在返回，再找一条路，找到头，再返回······（下图是一棵二叉树的深搜顺序）：

这是核心代码框架：

void dfs(int x)
{
    if(x == n)
    {
        // 找到一种结果，统计个数或输出路径。
        return ;
    }
    for(int i = 0;i < n;i++)
    {
        if(!visit[i]/* 检查 i 是否用过 */ && /* 是否可以使用 i 的其他条件 */) 
        {
            visit[i] = 1; // 将 i 标记为用过。
            dfs(x + 1);
            visit[i] = 0; // 回溯，搜索过 i 后 i 就可以使用了。
        }
    }
}

2.深搜的分支

1.搜索路径

搜索路径是深搜的重要分支，提到搜索路径，你应该能想到如下代码：

void dfs(int x,int y)
{
    if(x == end_x && y == end_y)
    {
        // 找到一种结果，统计个数或输出路径。
        return ;
    }
    
    if(!visit[x + 1][y]/* 检查 x+1,y 是否走过 */ && x + 1 <= n/*没出界*/ &&/* x+1,y 是否可以走，是不是障碍物 */) 
    {
        visit[x + 1][y] = 1; // 将 x+1,y 标记为走过。
        dfs(x + 1,y);
        visit[x + 1][y] = 0; // 回溯，搜索过 x,y 后 x,y 就可以使用了。
    }
    if(!visit[x][y + 1] && y + 1 <= n &&/* x,y+1 是否可以走，是不是障碍物 */) 
    {
        visit[x][y + 1] = 1;
        dfs(x,y + 1);
        visit[x][y + 1] = 0;
    }
    if(!visit[x - 1][y] && x - 1 >= 1 &&/* x-1,y 是否可以走，是不是障碍物 */) 
    {
        visit[x - 1][y] = 1;
        dfs(x - 1,y);
        visit[x - 1][y] = 0;
    }
    if(!visit[x][y - 1] && y - 1 >= 1 &&/* x,y-1 是否可以走，是不是障碍物 */) 
    {
        visit[x][y - 1] = 1;
        dfs(x,y - 1);
        visit[x][y - 1] = 0;
    }
}

太长了~~（不要和头文件比较，考试不会让你写头文件）~~，可以开数组，加循环,但 x,y 两个变量怎么办？开两个数组。

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

这就有了新的 dfs 函数，可以把四个判断换成循环：

for(int i = 0;i < 4;i ++)
{
    int tx = x + dx[i];
    int ty = y + dy[i];
    if(tx >= 1 && tx <= n && ty >= 1 && ty <= n)
    {
        dfs(tx,ty);
    }
}

2.记忆化搜索

搜索时，难免有重复，怎么去重，那就把搜索到一个位置的答案存下来。

1.定义

定义 $ans_{x,y}$ 为搜索到 x,y 时的答案。

2.更新

只要在函数结束时更新答案即可。

3.剪枝

如果 $ans_{x,y} \neq 0$ （说明有了答案）即可直接返回答案。

3.例题

1.深さ優先探索

1.题目描述

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。

现在给出地图：

s：代表高桥先生的家

g：代表鱼店

.：代表道路

#：代表墙壁

高桥先生不能穿过墙壁。

2.代码

#include <iostream>
using namespace std;
bool mp[502][502];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int x2,y2;
bool f;
void dfs(int n,int m)
{
    if(n == x2 && m == y2) f = true; // 搜索结束，找到答案。
    if(f) return ; // 有了答案，不用继续搜索了。
    if(!mp[n][m]) return ; // 不能走
    mp[n][m] = 0; // 标记走过，防止重复
    for(int i = 0;i < 4;i ++){
        dfs(n + dx[i],m + dy[i]); // 搜索下一个
    }
    return ;
}
int main()
{
    int n,m,x1,y1;
    char temp;
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> temp;
            if (temp == '.'){
                mp[i][j] = true;
            }
            else if(temp == 's'){
                x1 = i;
                y1 = j;
                mp[i][j] = true;
            }
            else if(temp == 'g'){
                x2 = i;
                y2 = j;
            }
        }
    }
    dfs(x1,y1);
    if(f) cout << "Yes";
    else cout << "No";
    return 0;
}

请勿抄袭代码！！！

详见洛谷社区规则：

用户有如下违反学术诚信的行为，视情节严重性，可处以警告或棕名的处罚：

评测时多次提交抄袭他人的代码；
在公开比赛期间作出洛谷公开比赛参赛规则提到的违反学术诚信行为；
提交题解审核的博客中，含有抄袭他人的内容；
其他违反洛谷学术诚信的行为

2.滑雪

本题仅提供思路：

1.请记忆化搜索！

2.注意不走回头路!

二、广度优先搜索

1.简介

和深搜不一样，广度优先搜索（简称广搜）又称层次遍历，顾名思义，一层一层的搜索：

怎么实现呢？总不能搞一个数组存顺序吧？不用， c++ STL 中自带 queue （队列）我们可以用队列代替数组，存搜索顺序。每此从队列中拿出一个元素，如果是最后一个元素，就 break ，统计路径或输出，否则就把他的子节点入队。注意⚠️：要先把第一个节点入队，要不然什么也搜不到！！！

queue <int> q;
while(!q.empty())
{
    int start = q.front(); // 拿出队首元素
    q.pop(); // 出队一个元素
    if(start == n)
    {
        // 找到一条路，处理。
    }
    for(int i = 0;i < mp[start].size();i ++)
    {
        q.push(mp[start][i]); // 入队它的字节点
    }
}

2.例题

马的遍历：

1.题目描述

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

2.代码

#include<iostream>
#include<queue>
#include<map>
using namespace std;
int b[401][401],n,m;
int dx[8] = {1,1,2,2,-1,-1,-2,-2};
int dy[8] = {2,-2,1,-1,2,-2,1,-1};

int main(){
    int x,y;
    queue <pair<int,int> > q;
    cin >> n >> m >> x >> y;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            b[i][j] = -1;
        }
    }
    b[x][y] = 0;
    q.push(make_pair(x,y));
    while(!q.empty()) {
        int x0 = q.front().first;
        int y0 = q.front().second;
        q.pop();
        for(int i = 0;i < 8;i ++){
            int x1 = x0 + dx[i],y1 = y0 + dy[i];
            if(x1 > n || x1 < 1 || y1 > m || y1 < 1 || b[x1][y1] != -1)  continue;
            b[x1][y1] = b[x0][y0] + 1;
            q.push(make_pair(x1,y1));
        }
    }
    
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cout << ' ' << b[i][j];
        }
        cout << endl;
    }
    return 0;
}

你学会了吗？