首页 > 编程语言 >C++U5-06-广度优先搜索3

C++U5-06-广度优先搜索3

时间:2023-11-20 15:33:27浏览次数:41  
标签:count 06 tem U5 C++ int mp && push

广搜逻辑

 

 广搜代码核心思路

 广搜伪代码

前面讲解的广度优先搜索案例都类似迷宫类的问题,但有些非迷宫类问题也可以使用广搜的思路解决

[【广搜】转弯]

【算法分析】
可以以转弯次数为依据进行广搜,这样就是每一个方向都走到尽头。特别要注意的是当这个位置访问过,还是要继续要向这个方向走,因为后面可能有没有访问过的位置。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

char MAP[109][109];
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
struct node {
    int x, y, step;
}l,r;
bool vis[109][109];
int main() {
    int n;
    cin >> n;
    int sx, sy, ex, ey;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            getchar();
            cin >> MAP[i][j];
        }
        for (int j = 1; j <= n; j++) {
            if (MAP[i][j] == 'A') sx = i, sy = j;
            else if (MAP[i][j] == 'B') ex = i, ey = j;
        }
    }
    queue<node> q;
    q.push({ sx,sy,0 });
    vis[sx][sy] = 1;
    while (q.size()) {
        r = q.front();
        q.pop();
        if (r.x == ex && r.y == ey) {
            cout << r.step - 1;
            break;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 1;; j++) {
                l.x = r.x + j * dir[i][0], l.y = r.y + j * dir[i][1], l.step = r.step + 1;
                if (l.x >= 1 && l.x <= n && l.y >= 1 && l.y <= n && MAP[l.x][l.y] != 'x' ) {
                    if (!vis[l.x][l.y]) {
                        vis[l.x][l.y] = 1;
                        q.push(l);
                    }
                }
                else break;
            }
        }
    }
    if (!vis[ex][ey]) cout << -1;
    return 0;
}
View Code

 

[【广搜】最小基因变化]   map和set数据类型使用在下面

 

【算法分析】
从 start 字符串开始进行广搜,每次只变化一个字符。可以用 map 来记录达到某个字符串所需的最小次数。用 set 存储基因库,用于快速判断基因是否在基因库中。

【参考代码】
#include<bits/stdc++.h>
using namespace std;


int main() {
    string start, end;
    cin >> start >> end;
    int n;
    cin >> n;
    set<string> se;
    for (int i = 0; i < n; i++) {
        string a;
        cin >> a;
        se.insert(a);
    }
    map<string, int> mp;
    mp[start] = 0;
    queue<string> q;
    q.push(start);
    while (q.size()) {
        string r = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            string tem = r;
            tem[i] = 'A';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'C';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'G';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }

            tem[i] = 'T';
            if (!mp.count(tem) && se.count(tem)) {
                mp[tem] = mp[r] + 1;
                q.push(tem);
            }
        }
    }
    if (mp.count(end)) cout << mp[end];
    else cout << -1;
    return 0;
}
View Code

 

set集合

 map容器

 程序阅读题

 选项

 

 

 

 

 总结

 

标签:count,06,tem,U5,C++,int,mp,&&,push
From: https://www.cnblogs.com/jayxuan/p/17844070.html

相关文章

  • C++第三方库汇总
    图像处理:OpenCV矩阵运算:Eigen图像读写:stb_image,广泛应用于Graphics领域文件解析json文件解析:RapidJson,参考:https://www.geeksforgeeks.org/rapidjson-file-read-write-in-cpp/glTF文件解析:cgltf......
  • C++U4-第05课-二分查找
    上节课作业部分(点击跳转)  引入分治算法概念  二分法分治思想编程题  二分查找能解决的问题不仅仅是找到一个值 题1: 要在一个有序序列中查找一个数,可以使用二分算法。include<iostream>usingnamespacestd;intBinarySearch(inta[],intl,......
  • MIT18.06Linear Algebra 第12讲 图、网络、关联矩阵
    转载于:超详细MIT线性代数公开课笔记......
  • C++U3-第1课-基础排序(一)
    学习目标排序的概念  本阶段会学习的排序有 冒泡排序概念 第一轮比较,与交换 例题1:一趟交换 例题2:多躺比较,冒泡排序 【题意分析】进行n-1趟冒泡排序的过程,每一次输出当前一趟冒泡排序完的结果【思路分析】定义一个n,输入当前的n和储存n个数的数组for......
  • C++使用OpenSSL实现AES-256-CBC加密解密实例----亲测OK
    摘自:https://blog.csdn.net/GerZhouGengCheng/article/details/106103039//AesUtil.h#ifndef__AES_UTIL_H__#define__AES_UTIL_H__#ifdef__cplusplus//告诉编译器,这部分代码按C语言的格式进行编译,而不是C++的extern"C"{#endifstringUTIL_aes_cbc_e......
  • openssl做HMAC实例(C++)----自测OK
    摘自:https://blog.csdn.net/mijichui2153/article/details/1047414601、HMAC简介(1)MAC(MessageAuthenticationCode,消息认证码算法),可以将其认为是含有秘钥的散列(Hash)函数算法;即兼容了MD和SHA算法,并在此基础上加上了秘钥。因此MAC算法也经常被称作HMAC算法。当然HMAC就是“基......
  • openssl做HMAC实例(C++)原文
    摘自:https://blog.csdn.net/mijichui2153/article/details/1047414601、HMAC简介(1)MAC(MessageAuthenticationCode,消息认证码算法),可以将其认为是含有秘钥的散列(Hash)函数算法;即兼容了MD和SHA算法,并在此基础上加上了秘钥。因此MAC算法也经常被称作HMAC算法。当然HMAC就是“基......
  • 一万五千字C++STL【容器】详解(转载)
    一、什么是容器?所谓容器,就是可以承载,包含元素的一个器件,它是STL六大组件之一,是容器、算法、迭代器中最重要也是最核心的一部分。二、STL中各大容器的结构与分类2.1顺序性容器2.1.1什么是顺序性容器?顺序性容器就是将一组具有相同类型的元素以严格的线性形式组织起来2.1.2......
  • [实验任务一]:JAVA和C++常见数据结构迭代器的使用
    信1305班共44名同学,每名同学都有姓名,学号和年龄等属性,分别使用JAVA内置迭代器和C++中标准模板库(STL)实现对同学信息的遍历,要求按照学号从小到大和从大到小两种次序输出学生信息。实验要求:1. 搜集并掌握JAVA和C++中常见的数据结构和迭代器的使用方法,例如,vector,list,map和set等......
  • 十四.SPI使用1——SPI基础和ICM20608的使用
    在日常设备使用中,最常用通讯协议就是I2C和SPI了,前面过了一遍I2C,I2C接口速度最快能到400K,但是SPI能到几时兆。下面我们来实现SPI的使用。SPI接口SPI硬件定义SPI和I2C一样属于一种串行通讯协议,但是I2C需要2根线实现通讯,这样就限制了传输的速度;SPI则需要4根线才能数据通信(如果是......