搜索算法（DFS和BFS 蓝桥杯 C++）

news/2024/6/29 12:02:08 标签: 深度优先, 宽度优先, 蓝桥杯, c++, 算法

目录

题目一（N皇后问题）： 

代码：

 题目二（路径之谜）：

代码：

 题目三（最大数字）：

代码：

题目四（长草）：

代码：

 题目五（走迷宫）：

代码：

 题目六（迷宫）：

​代码：

题目一（N皇后问题）： 

代码：

#include<iostream>
using namespace std;
int ans = 0;
int n;
int a[20] = { 0 };
int judge(int k)
{
    for (int i = 1; i < k; i++)//从第一行到第k-1行上有无与第k行第a[k]列冲突的皇后
    {
        if ((abs(k - i) == abs(a[k] - a[i])) || (a[k] == a[i]))//斜线和同一列
            return 0;//同一斜线说明斜率为1或者-1，则x1-x2/y1-y2=1,即x1-x2=y1-y2
    }
    return 1;
}

int check(int a)
{
    if (a > n)
        ans++;
    else
        return 0;
    return 1;
}

void dfs(int k)
{
    if (check(k))
        return;
    else
    {
        for (int i = 1; i <= n; i++)
        {
            a[k] = i;//第k个皇后放的列数
            if (judge(k))//判断第k个皇后是否可放在a[k]该列
                dfs(k + 1);//可放，进行下一个皇后位置
            else
                continue;//不可放，则下一列
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);//从第一个皇后开始放
    cout << ans << endl;
}

 题目二（路径之谜）：

代码：

#include<iostream>
#include<vector>
using namespace std;
int rol[25], col[25];
int n;
int book[25][25];//标记是否走过
int dx[4] = { 0,1,-1,0 };
int dy[4] = { 1,0,0,-1 };
typedef struct node
{
    int a, b;
}node;
vector <node> res;
int check(int x, int y)
{
    if (x == n && y == n)//走到终点
    {
        for (int i = 1; i <= n; i++)
        {
            if (col[i] != 0 || rol[i] != 0)//有一个箭靶上面还有箭，则说明不符合
                return 0;
        }
        for (int i = 0; i < res.size(); i++)//箭靶都拔光了，符合
        {
            int tx = res[i].a;
            int ty = res[i].b;
            int sum = n * (tx - 1) + ty - 1;//算出第几格，输出
            cout << sum << " ";
        }
        return 0;
    }
    return 1;//没走到终点，继续走
}
void dfs(int x, int y)
{
    if (!check(x, y))//判断是否继续往下走
        return;
    else
    {
        for (int i = 0; i < 4; i++)//朝四个方向走
        {
            int tx = dx[i] + x;
            int ty = dy[i] + y;
            if (book[tx][ty] == 1 || tx<1 || tx>n || ty<1 || ty>n || col[tx] <= 0 || rol[ty] <= 0)//走过或者走出边界或者箭靶上的箭数量不够(等于0也不行,是因为在之前已经判断还没走到终点，如果箭的数量等于0，也意味着不可以走到这)
                continue;
            else
            {
                book[tx][ty] = 1;//标记该点走过
                col[tx]--, rol[ty]--;//靶子上的数减1
                res.push_back({ tx,ty });//走过的存下
                dfs(tx, ty);//从tx,ty往下走递归
                res.pop_back();//恢复
                book[tx][ty] = 0;
                col[tx]++;
                rol[ty]++;
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> rol[i];
    for (int i = 1; i <= n; i++)
        cin >> col[i];
    book[1][1] = 1;
    rol[1]--, col[1]--;
    res.push_back({ 1,1 });
    dfs(1, 1);
    //cout << 1;
}

 题目三（最大数字）：

代码：

#include<iostream>
using namespace std;
string s;
long long ans = 0;
int n, m;
void dfs(int i, long long sum)
{
    int x = s[i] - '0';//第i位数
    if (s[i])//有该位数
    {
        int t = min(n, 9 - x);//看操作数一的次数够不够满足该位加到9
        n -= t;
        dfs(i + 1, sum * 10 + x + t);
        n += t;//回溯
        if (m >= x + 1)//对于操作数二，只有够让该位减为9，才能使其变大
        {
            m -= x + 1;
            dfs(i + 1, sum * 10 + 9);
            m += x + 1;//回溯
        }
    }
    else
        ans = max(ans, sum);//取最大值
}
int main()
{
    cin >> s;
    cin >> n >> m;
    dfs(0, 0);
    cout << ans;
}

题目四（长草）：

代码：

#include<iostream>
#include<queue>
using namespace std;
int n, m, k;
char s[1010][1010];
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
int len;
typedef struct node
{
    int x, y;
}node;
queue<node> q;
void bfs()
{
    while (!q.empty()&&k>0)
    {
        int x = q.front().x ;
        int y = q.front().y ;
        q.pop();
        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>m || s[tx][ty]=='g')
                continue;
            else 
            {
                s[tx][ty] = 'g';
                q.push({ tx, ty });
            }
        }
        len--;//每取一块地，则len--
        if (len == 0)//len等于0则表明，该月都长完了
        {
            k--;//则k--
            len = q.size();//再取该月有多少地要向周围生长
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> s[i][j];
            if (s[i][j] == 'g')
            {
                q.push({ i,j });//是草的入队
            }
        }
    cin >> k;
    len = q.size();//初始一共有几块地为草
    bfs();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << s[i][j];
        }
        cout << endl;
    }
}

 题目五（走迷宫）：

代码：

#include<iostream>
#include<queue>
using namespace std;
int n, m, k;
int s[110][110];
int book[110][110] = { 0 };
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
int flag = 0;//标志是否能走通迷宫
typedef struct node
{
    int x, y, s;
}node;
node start, end1;
queue<node> q;
int check(int x, int y)//检查是否到达出口
{
    if (x == end1.x && y == end1.y)
        return 1;
    return 0;
}
void bfs()
{
    while (!q.empty())
    {
        int x = q.front().x;//取x坐标
        int y = q.front().y;//取y坐标
        int step = q.front().s;//取步数
        q.pop();
        if (check(x,y))//检查是否到达出口
        {
            cout << step;
            flag = 1;//标记走出迷宫
            return;
        }
        for (int i = 0; i < 4; i++)//遍历四个方向
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx<1 || ty<1 || tx>n || ty>m || book[tx][ty]==1 ||s[tx][ty]==0)//是否越界，是否走过，是否可走
                continue;
            else
            {
                book[tx][ty] = 1;
                q.push({ tx,ty,step+1 });
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> s[i][j];
        }
    cin >> start.x >> start.y >> end1.x >> end1.y;
    q.push({ start.x,start.y,0 });
    bfs();
    if (flag == 0)
        cout << "-1";
}

 题目六（迷宫）：

 代码：

#include<iostream>
#include<queue>
using namespace std;
string s[100] = { "01010101001011001001010110010110100100001000101010",
           "00001000100000101010010000100000001001100110100101",
           "01111011010010001000001101001011100011000000010000",
           "01000000001010100011010000101000001010101011001011",
           "00011111000000101000010010100010100000101100000000",
           "11001000110101000010101100011010011010101011110111",
           "00011011010101001001001010000001000101001110000000",
           "10100000101000100110101010111110011000010000111010",
           "00111000001010100001100010000001000101001100001001",
           "11000110100001110010001001010101010101010001101000",
           "00010000100100000101001010101110100010101010000101",
           "11100100101001001000010000010101010100100100010100",
           "00000010000000101011001111010001100000101010100011",
           "10101010011100001000011000010110011110110100001000",
           "10101010100001101010100101000010100000111011101001",
           "10000000101100010000101100101101001011100000000100",
           "10101001000000010100100001000100000100011110101001",
           "00101001010101101001010100011010101101110000110101",
           "11001010000100001100000010100101000001000111000010",
           "00001000110000110101101000000100101001001000011101",
           "10100101000101000000001110110010110101101010100001",
           "00101000010000110101010000100010001001000100010101",
           "10100001000110010001000010101001010101011111010010",
           "00000100101000000110010100101001000001000000000010",
           "11010000001001110111001001000011101001011011101000",
           "00000110100010001000100000001000011101000000110011",
           "10101000101000100010001111100010101001010000001000",
           "10000010100101001010110000000100101010001011101000",
           "00111100001000010000000110111000000001000000001011",
           "10000001100111010111010001000110111010101101111000" };
int n, m, k;
int book[110][110] = { 0 };
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,-1,1,0 };
string dt[4] = { "D","L","R","U" };//按字典序排序
typedef struct node
{
    int x, y;
    string t;
}node;
node start, end1;
queue<node> q;
int check(int x, int y)//检查是否到达出口
{
    if (x == end1.x && y == end1.y)
        return 1;
    return 0;
}
void bfs()
{
    while (!q.empty())
    {
        int x = q.front().x;//取x坐标
        int y = q.front().y;//取y坐标
        string t = q.front().t;//取步骤
        q.pop();
        if (check(x, y))//检查是否到达出口
        {
            cout << t;
            return;
        }
        for (int i = 0; i < 4; i++)//遍历四个方向
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            string tt = t + dt[i];
            if (tx<0 || ty<0 || tx>29 || ty>49)//是否越界
                continue;
            else if(book[tx][ty]==0&&s[tx][ty]=='0')
            {
                book[tx][ty] = 1;
                q.push({ tx,ty,tt });
            }
        }
    }
}
int main()
{
    start.x = 0, start.y = 0, end1.x = 29, end1.y = 49;
    q.push({ 0,0 ,"" });
    bfs();
}


http://www.niftyadmin.cn/n/5406354.html

相关文章

算法比赛|赛制介绍| ACM, IOI赛制, OI赛制

算法比赛|赛制介绍| ACM, IOI赛制, OI赛制

&#x1f525;博客介绍&#xff1a; 27dCnc &#x1f3a5;系列专栏&#xff1a; <<数据结构与算法>> << 算法入门>> << C项目>> &#x1f3a5; 当前专栏: << 算法入门>> 专题 : 数据结构帮助小白快速入门算法 &#x1f4…
阅读更多...
如何学习openfoam

如何学习openfoam

学习OpenFOAM的详细步骤、流程、学习网站、练习案例以及B站学习资源推荐如下&#xff1a; 一、详细步骤和流程 安装OpenFOAM&#xff1a;首先&#xff0c;你需要在你的计算机上安装OpenFOAM。你可以从OpenFOAM的官方网站下载适合你的操作系统的安装包&#xff0c;然后按照官方提…
阅读更多...
java接口+vue后台管理+uniapp前端 移动端商城

java接口+vue后台管理+uniapp前端 移动端商城

花了半个月时间用的 nuoyi的Java系统,https://www.ruoyi.vip前后端分离版开发的商城 UI和前端用的别的大神模板套用https://ext.dcloud.net.cn/plugin?id1531 正常下单流程&#xff0c;没有开发支付功能。后面开发了再上传 演示地址http://mall.meanwellsps.com 下载地址…
阅读更多...
java面试题（spring框架篇）（黑马 ）

java面试题（spring框架篇）（黑马 ）

树形图&#xff1a; 一、Spring框架种的单例bean是线程安全吗&#xff1f; Service Scope("singleton") public class UserServiceImpl implements UserService{ } singleton:bean在每个Spring IOC容器中只有一个实例 protype&#xff1a;一个bean的定义可以有多个…
阅读更多...
C++ //练习 10.22 重写统计长度小于等于6 的单词数量的程序，使用函数代替lambda。

C++ //练习 10.22 重写统计长度小于等于6 的单词数量的程序，使用函数代替lambda。

C Primer&#xff08;第5版&#xff09; 练习 10.22 练习 10.22 重写统计长度小于等于6 的单词数量的程序&#xff0c;使用函数代替lambda。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /********************************…
阅读更多...
markdown笔记(自用)

markdown笔记(自用)

一.标题语法#空格&#xff0c;几个#就是几级标题 四级标题<H> 二.段落语法 用空白行分开 你好 三.换行 在一行的末尾添加两个或多个空格&#xff0c;然后 v vvvvv 按回车键,即可创建一个换行()。 换行与段落的区别在于换行后两行是挨着的&#xff0c;而段落之间有一…
阅读更多...
Leetcode150二刷总结

Leetcode150二刷总结

滑动窗口&#xff08;ok&#xff09; 题号&#xff1a;3、209、76 定义好窗口的左边界left和右边界right一般是只需要遍历right&#xff0c;满足条件后调整left 链表 题号&#xff1a;206、92、146、25、21 反转链表主要是设置好pre&#xff08;初始为null&#xff09;和c…
阅读更多...
docker部署aria2-pro

docker部署aria2-pro

前言 我平时有一些下载视频和一些资源文件的需求&#xff0c;有时候需要离线下载&#xff0c;也要速度比较快的方式 之前我是用家里的玩客云绝育之后不再写盘当下载机用的&#xff0c;但是限制很多 我发现了aria2 这个下载器非常适合我&#xff0c;而有个大佬又在原来的基础…
阅读更多...
最新文章

Copyright @ 2022~2023