kuangbin专题——简单搜索

1.棋盘问题（dfs）

在这里插入图片描述
在这里插入图片描述

思路

1.dfs 参数里枚举每一行，然后在里面弄两个分支，选或者不选，选的话就枚举这一行的所有元素
2.注意最后一行要先判断，再返回

#include<iostream>
using namespace std;
const int N = 10;
char g[N][N];
int b[N];
int n, k, res;

// 枚举每一行，记录当前选了几个棋
void dfs(int u, int cnt){
    if(cnt == k){
        res++;
        return;
    }
    // 这个要放在后面，防止没有判断最后一行
    if(u > n) return;
    // 选，枚举这一行的所有元素
    for(int i = 1; i <= n; i++){
        if(g[u][i] == '#' && !b[i]){
            b[i] = 1;
            dfs(u + 1, cnt + 1);
            b[i] = 0;
        }
    }
    // 不选
    dfs(u + 1, cnt);
}

int main(){
    while(cin>>n>>k && (n != -1 && k != -1)){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                cin>>g[i][j];
            }
        }
        res = 0;
        dfs(1, 0);
        cout<<res<<endl;
    }
    return 0;
}

2.地牢大师（bfs）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

思路

由二维扩展到了三维，多加一个 dz[] 数组

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
struct P{
    int x, y, z;
};
char g[N][N][N];
int dis[N][N][N];
P q[N * N * N];
int l, r, c;

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

int bfs(P st, P ed){
    // 每次要清空队列
    memset(q, 0, sizeof(q));
    int hh = 0, tt = -1;
    memset(dis, -1, sizeof(dis));
    dis[st.x][st.y][st.z] = 0;
    q[++tt] = st;
    while(hh <= tt){
        P t = q[hh++];
        for(int i = 0; i < 6; i++){
            int x = t.x + dx[i], y = t.y + dy[i], z = t.z + dz[i];
            // 出界
            if(x < 1 || x > l || y < 1 || y > r || z < 1 || z > c) continue;
            // 遇到障碍物
            if(g[x][y][z] == '#') continue;
            // 已经走过
            if(dis[x][y][z] != -1) continue;
        
            dis[x][y][z] = dis[t.x][t.y][t.z] + 1;
            if(x == ed.x && y == ed.y && z == ed.z) return dis[x][y][z];
            
            q[++tt] = {x, y, z};
        }
    }
    return -1;
}

int main(){
    P st, ed;
    while(cin>>l>>r>>c && (l || r || c)){
        for(int i = 1; i <= l; i++){
            for(int j = 1; j <= r; j++){
                for(int k = 1; k <= c; k++){
                    cin>>g[i][j][k];
                    if(g[i][j][k] == 'S') st = {i, j, k};
                    if(g[i][j][k] == 'E') ed = {i, j, k};
                }
            }
        }
        int res = bfs(st, ed);
        if(res == -1) cout<<"Trapped!"<<endl;
        else cout<<"Escaped in "<<res<<" minute(s)."<<endl;
    }
    return 0;
}

3.抓住那头牛（bfs）

在这里插入图片描述

思路

bfs 搜索每种情况，最先到达 k 的时候，一定是最短的时间

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5;
pair<int, int> q[N + 10];
int hh, tt = -1;
int b[N + 10];
int n, k;

int bfs(int u){
    q[++tt] = make_pair(u, 0);
    while(hh <= tt){
        auto it = q[hh++];
        // 最先找到的一定是花费时间最短的
        if(it.first == k) return it.second;
        if(it.first + 1 >= 0 && it.first + 1 <= N && !b[it.first + 1]){
            b[it.first + 1] = 1;
            q[++tt] = make_pair(it.first + 1, it.second + 1);
        }
        if(it.first - 1 >= 0 && it.first - 1 <= N && !b[it.first - 1]){
            b[it.first - 1] = 1;
            q[++tt] = make_pair(it.first - 1, it.second + 1);
        }
        if(2 * it.first >= 0 && 2 * it.first <= N && !b[2 * it.first]){
            b[2 * it.first] = 1;
            q[++tt] = make_pair(2 * it.first, it.second + 1);
        }
    }
}

int main(){
    scanf("%d%d", &n, &k);
    if(n >= k){
        printf("%d", n - k);
        return 0;
    }
    int res = bfs(n);
    printf("%d", res);
    return 0;
}

4.翻转（dp）

在这里插入图片描述
在这里插入图片描述

思路

二进制枚举第一行所有情况，因为每一行都可以影响它的上一行

#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
int g[N][N], b[N][N];
int p[N][N], q[N][N];
int n, m;

void t(int x, int y){
    int dx[] = {1, -1, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0};
    for(int i = 0; i < 5; i++){
        int aa = x + dx[i], bb = y + dy[i];
        if(aa < 0 || aa >= n || bb < 0 || bb >= m) continue;
        g[aa][bb] ^= 1;
    }
}

void dp(){
    int res = 1e9;
    // 枚举第一行所有情况
    for(int k = 0; k < (1 << m); k++){
        int cnt = 0;
        memcpy(b, g, sizeof(g));
        memset(p, 0, sizeof(p));
        for(int i = 0; i < m; i++){
            if(k >> i & 1){
                t(0, i);
                cnt++;
                p[0][i] = 1;
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                if(g[i - 1][j]){
                    t(i, j);
                    cnt++;
                    p[i][j] = 1;
                }
            }
        }
        int flag = 1;
        for(int i = 0; i < m; i++){
            if(g[n - 1][i]){
                flag = 0;
                break;
            }
        }
        if(flag){
            if(cnt < res){
                res = cnt;
                memcpy(q, p, sizeof(p));
            }
        }
        memcpy(g, b, sizeof(b));
    }
    if(res != 1e9){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                printf("%d ", q[i][j]);
            }
            printf("\n");
        }
    }else printf("IMPOSSIBLE");
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d", &g[i][j]);
        }
    }
    dp();
    return 0;
}

5.找倍数（bfs）

在这里插入图片描述
在这里插入图片描述

思路

搜索每一位是 0 和 1，直到找到符合条件的数，队列可能会存储 2 的 100 次方个数，不能用数组模拟，100 之内的倍数会爆 int，记得开 long long

#include<iostream>
#include<queue>
using namespace std;
int n;

int main(){
    while(cin>>n && n){
        queue<long long> q;
        // 因为是非 0 倍数 m，从 1 开始搜索
        q.push(1);
        while(q.size()){
            long long it = q.front();
            q.pop();
            if(it % n == 0){
                cout<<it<<endl;
                break;
            }
            // 搜索 1
            q.push(it * 10 + 1);
            // 搜索 0
            q.push(it * 10);
        }
    }
    return 0;
}

6.质数路径（bfs）

在这里插入图片描述
在这里插入图片描述

思路

1.先用线性筛质数
2.再用搜索每一种情况，一共有 39 * 38 * 37… 种情况，首位不能为 0

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4;
int primes[N], st[N];
int dis[N];
int t, a, b;

// 线性筛质数
void init(int n){
    int cnt = 0;
    for(int i = 2; i <= n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

int main(){
    init(9999);
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &a, &b);
        memset(dis, -1, sizeof(dis));
        dis[a] = 0;
        int q[N] = {0}, hh = 0, tt = - 1;
        // 存储每一位
        int num[4], sca[4] = {1000, 100, 10, 1};
        q[++tt] = a;
        while(hh <= tt){
            int it = q[hh++];
            // 存储每一位
            for(int i = it, j = 3; i > 0; i /= 10, j--) num[j] = i % 10;
            
            // 枚举39种情况
            for(int i = 0; i < 4; i++){
                for(int j = 0; j < 10; j++){
                    // 去掉首位为 0 的情况
                    if(!i && !j) continue;
                    // 改变第 i 位的数
                    int res = it + (j - num[i]) * sca[i];
                    // st 数组中被标记为 1 的就不是质数
                    if(!st[res] && dis[res] == -1){
                        q[++tt] = res;
                        dis[res] = dis[it] + 1;
                    }
                }
            }
        }
        printf("%d\n", dis[b]);
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/430917.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

uniapp制作--进步器的选择

uniapp制作--进步器的选择

介绍&#xff1a; 进步器的选择,一般用于商城购物选择物品数量的场景 注意&#xff1a;该输入框只能输入大于或等于0的整数 效果展示&#xff1a; 代码展示&#xff1a; 以下是一个简单的购物车页面示例&#xff0c;包括选择商品和显示数量的功能&#xff1a; 在这个示例中…
阅读更多...
docker 安装 Jenkins

docker 安装 Jenkins

一、安装 jenkins 中文文档&#xff1a; https://www.jenkins.io/zh/doc/book/installing/#docker jenkins 提供了详细的安装方式和步骤&#xff0c;这里咱们使用 docker 进行安装 根据文档上的命令&#xff0c;自己修改如下&#xff1a; docker run \ -u root \ --name jenki…
阅读更多...
三八妇女节送礼推荐：送给她的五款超值好物，绝不踩雷！

三八妇女节送礼推荐：送给她的五款超值好物，绝不踩雷！

随着三八妇女节的临近&#xff0c;我们开始思考如何向身边的女性表达我们的尊重和关爱。这个特殊的节日不仅是对女性贡献的认可&#xff0c;更是展示我们关怀与感激之情的绝佳时机。在众多礼物中&#xff0c;如何挑选一份既能体现心意又实用的礼品呢&#xff1f;为了让您在这个…
阅读更多...
Win UI3开发笔记（八）多语言切换

Win UI3开发笔记（八）多语言切换

要实现的目标&#xff1a;checkbox选定什么语言&#xff0c;当前应用程序的文字就是这一门语言。 步骤如下&#xff1a; 参考现有的一个程序的代码&#xff0c;先定义资源文件。 如果只有一个按钮、一个文本、一个列表框的话 新建String 在这个文件夹下定义en-us&#xff0c;z…
阅读更多...
智能物联时代下RFID技术在汽车零部件智能制造中的引领作用

智能物联时代下RFID技术在汽车零部件智能制造中的引领作用

RFID&#xff08;Radio Frequency Identification&#xff0c;射频识别&#xff09;技术在汽车零部件加工中有广泛的应用&#xff0c;其工作原理是通过无线电频率进行自动识别。在汽车零部件加工中&#xff0c;RFID技术可以发挥重要作用&#xff0c;提高生产效率、降低成本和减…
阅读更多...
LVS集群（Linux Virtual server）相关介绍及LVS的NAT模式部署

LVS集群（Linux Virtual server）相关介绍及LVS的NAT模式部署

群集的含义 ●Cluster&#xff0c;集群、群集由多台主机构成&#xff0c;但对外只表现为一个整体&#xff0c;只提供访问入口(域名或IP地址)&#xff0c;相当于一台大型计算机 问题&#xff1a; 互联网应用中&#xff0c;随着站点对硬件性能、响应速度、服务稳定性、数据可靠…
阅读更多...
网络工程师笔记7

网络工程师笔记7

路由器需要知道下一跳和出接口才能把数据转发出去 各个协议的优先级 直连&#xff1a;0 OSPF&#xff1a;10 ISIS&#xff1a;15 静态&#xff1a;60 RIP :100 静态路由 ip route-static <目的ip地址> 掩码 下一跳地址 例…
阅读更多...
哈希的简单介绍

哈希的简单介绍

unordered系列关联式容器 在C98中&#xff0c;STL提供了底层为红黑树结构的一系列关联式容器&#xff0c;在查询时效率可达到 l o g 2 N log_2 N log2​N&#xff0c;即最差情况下需要比较红黑树的高度次&#xff0c;当树中的节点非常多时&#xff0c;查询效率也不理想。最好的…
阅读更多...
开展“3·15”金融消费者权益保护教育宣传活动怎样联系媒体投稿？

开展“3·15”金融消费者权益保护教育宣传活动怎样联系媒体投稿？

在组织“315”金融消费者权益保护教育宣传活动时,传统的方式通常是银行、金融机构或其他主办单位主动联系各类媒体,包括但不限于电视台、广播电台、报纸、杂志、新闻网站、金融专业媒体、社交媒体平台等,通过邮件、电话、传真等方式提供活动新闻稿、宣传材料、现场照片等素材,请…
阅读更多...
列车调度——典型的验证栈的出栈合不合法的问题，值得一看

列车调度——典型的验证栈的出栈合不合法的问题，值得一看

题目描述 有n列火车按照1,2,3...n的顺序排列&#xff0c;现所有的火车需要掉头&#xff0c;所以需要火车先驶入一个调度站&#xff0c;再开出来。 由于只有一根铁轨&#xff0c;所以要么最前面的一辆火车进去调度站&#xff0c;要么调度栈内最上面一辆火车开出调度栈。 现给…
阅读更多...
图书馆管理系统（1）

图书馆管理系统（1）

图书馆管理系统的框架图 图书馆管理系统的基本的功能代码&#xff0c;就是围绕上面这幅图的内容来写&#xff0c; 其中大一点的模块相当于主菜单&#xff0c;小一点的模块相当于子菜单&#xff0c;那就有了主菜单和子菜单如何响应&#xff08;主到子&#xff0c;子回主&#…
阅读更多...
使用Weaviate向量数据库：从Embeddings到Applications (Multilingual Search和RAG)

使用Weaviate向量数据库：从Embeddings到Applications (Multilingual Search和RAG)

Vector Databases: from Embeddings to Applications 课程地址&#xff1a;https://www.deeplearning.ai/short-courses/vector-databases-embeddings-applications/ 下面是这门课程的笔记。 使用Weaviate向量数据库&#xff1a;从Embeddings到应用&#xff0c;比如Multilin…
阅读更多...
【GIS技术】GIS在地质灾害易损性评价、危险性评估与灾后重建中的实践技术应用

【GIS技术】GIS在地质灾害易损性评价、危险性评估与灾后重建中的实践技术应用

地质灾害是指全球地壳自然地质演化过程中&#xff0c;由于地球内动力、外动力或者人为地质动力作用下导致的自然地质和人类的自然灾害突发事件。由于降水、地震等自然作用下&#xff0c;地质灾害在世界范围内频繁发生。我国除滑坡灾害外&#xff0c;还包括崩塌、泥石流、地面沉…
阅读更多...
[数据结构]队列

[数据结构]队列

1.队列的概念及结构 队列&#xff1a;只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出 FIFO(First In First Out) 入队列&#xff1a;进行插入操作的一端称为队尾 出队列&#xff1a;进行删除操作的一端称为队头 2…
阅读更多...
2024/3/5打卡线性DP--最长上升子序列**

2024/3/5打卡线性DP--最长上升子序列**

题目&#xff1a; 给定一个长度为 N 的数列&#xff0c;求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N。 第二行包含 N 个整数&#xff0c;表示完整序列。 输出格式 输出一个整数&#xff0c;表示最大长度。 数据范围 1≤N≤1000&#xff0c; −10^…
阅读更多...
密码安全：保护你的数据不被入侵的重要性

密码安全：保护你的数据不被入侵的重要性

title: 密码安全&#xff1a;保护你的数据不被入侵的重要性 date: 2024/3/5 17:54:56 updated: 2024/3/5 17:54:56 tags: 密码安全个人隐私保护身份盗窃防护金融损失防范弱密码危害安全密码创建双因素认证 在数字时代&#xff0c;密码安全是保护个人和机构数据的关键。然而&am…
阅读更多...
【python】堆排序

【python】堆排序

堆的概念 堆&#xff1a;一种特殊完全二叉树&#xff0c;也就是二叉树必须全部是满的&#xff0c;但是最后一排可以从右向左缺失。 大根堆&#xff1a;每个节点都比他的子节点大 小根堆&#xff1a;每个节点都比子节点小 堆在代码中的形式 堆在代码中实际上就是列表&#…
阅读更多...
制作耳机壳的UV树脂耳机壳UV胶和塑料材质有什么不同？

制作耳机壳的UV树脂耳机壳UV胶和塑料材质有什么不同？

制作耳机壳的UV树脂耳机壳UV胶和塑料材质有什么不同&#xff1f; 制作耳机壳的UV树脂和塑料材质在以下几个方面存在区别&#xff1a; 硬度与耐磨性&#xff1a;UV树脂具有较高的硬度和耐磨性&#xff0c;能够有效保护耳机内部零件&#xff0c;延长耳机使用寿命。而塑料材质相…
阅读更多...
四川首例强生全视人工晶体在成都爱尔眼科医院成功植入

四川首例强生全视人工晶体在成都爱尔眼科医院成功植入

【2024年3月1日&#xff0c;成都】全国首批、四川首例强生全视TECNIS Symfony™ Toric IOL植入手术在成都爱尔眼科医院成功开展&#xff0c;手术由爱尔眼科四川省区白内障学组组长、成都爱尔眼科医院副院长巫雷教授执刀。TECNIS Symfony™ Toric IOL的成功运用&#xff0c;不仅…
阅读更多...
每日学习总结20240301

每日学习总结20240301

20240301 1. strchr VS strrchr strchr和strrchr是C语言标准库中的字符串处理函数&#xff0c;用于在字符串中查找特定字符的位置。 1.1 strchr函数 strchr函数用于在字符串中查找第一次出现指定字符的位置&#xff0c;并返回该位置的指针。函数原型如下&#xff1a; char…
阅读更多...
最新文章

Copyright @ 2022~2023