题。。。。

 O - 胜利大逃亡(续)


题目分析 

        bfs+状态压缩(在bfs的基础上,存储持有不同钥匙时,此点位是否走过的情况);

-----状态压缩使用二进制实现,同时通过位运算修改是否转移至另一状态(详情见代码及注释)


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 35;struct demo{int x, y, val, key; //key用于存储钥匙情况
}st;int n, m, t;
char g[N][N];int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int bfs()
{bitset<1<<11> vis[N][N];// 1左移11位以分别存储11把钥匙的持有情况//0未持有,1持有vis[st.x][st.y][st.key] = 1;queue<demo> q;q.push(st);demo next, now;while(!q.empty()){now = q.front(); q.pop();for(int i = 0; i < 4; i++){next.x = now.x + dx[i]; next.y = now.y + dy[i];next.val = now.val + 1; next.key = now.key;if(next.x < 1 || next.y < 1 || next.x > n || next.y > m) continue;if(vis[next.x][next.y][next.key] || g[next.x][next.y] == '*') continue; //如果当前要进入的点在如今的状态走过,则跳过vis[next.x][next.y][next.key] = 1;if(next.val >= t) return -1;if(g[next.x][next.y] == '^') return next.val;if(g[next.x][next.y] >= 'A' && g[next.x][next.y] <= 'J'){int temp = g[next.x][next.y] - 'A';if(next.key & (1 << temp)) q.push(next);continue;}if(g[next.x][next.y] >= 'a' && g[next.x][next.y] <= 'j'){int temp = g[next.x][next.y] - 'a';next.key |= (1 << temp); //更新钥匙持有情况}q.push(next);}}return -1;
}int main()
{ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);while(cin >> n >> m >> t){for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> g[i][j];if(g[i][j] == '@'){st.x = i; st.y = j; st.val = st.key = 0;}}}cout << bfs() << '\n';}return 0;
}

 S - Key Task


题目分析 

        一样是bfs+状态压缩,但需要对数据进行处理,bitset开不下


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 120;struct demo{int x, y, val, key;
}st;int r, c;
char g[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};int bfs(){bitset<1 << 5> vis[N][N];demo next, now;queue<demo> q;vis[st.x][st.y][st.key] = 1;q.push(st);while(!q.empty()){now = q.front(); q.pop();for(int i = 0; i < 4; i++){next.x = now.x + dx[i]; next.y = now.y + dy[i];next.val = now.val + 1; next.key = now.key;if(next.x < 1 || next.y < 1 || next.x > r || next.y > c) continue;if(vis[next.x][next.y][next.key] || g[next.x][next.y] == '#') continue;vis[next.x][next.y][next.key] = 1;if(g[next.x][next.y] == 'X') return next.val;if(g[next.x][next.y] >= 'A' && g[next.x][next.y] <= 'Z'){int k;if(g[next.x][next.y] == 'B') k = 0;else if(g[next.x][next.y] == 'Y') k = 1;else if(g[next.x][next.y] == 'R') k = 2;else if(g[next.x][next.y] == 'G') k = 3;if(next.key & (1 << k))  q.push(next);continue;}if(g[next.x][next.y] >= 'a' && g[next.x][next.y] <= 'z'){int k;if(g[next.x][next.y] == 'b') k = 0;else if(g[next.x][next.y] == 'y') k = 1;else if(g[next.x][next.y] == 'r') k = 2;else if(g[next.x][next.y] == 'g') k = 3;next.key |= (1 << k);}q.push(next);}}return -1;
}int main()
{ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);while(cin >> r >> c){int ans = 0;if(r == 0 && c == 0) return 0;for(int i = 1; i <= r; i++){for(int j = 1; j <= c; j++){cin >> g[i][j];if(g[i][j] == '*'){st.x = i; st.y = j; st.val = st.key = 0;}}}ans = bfs();if(ans == -1) cout << "The poor student is trapped!" << '\n';else cout << "Escape possible in " << ans << " steps." << '\n';}return 0;
}

        状态压缩适用于存在大量状态的问题,进而实现将多个状态存于一个整数中


 B - Fliptile

 


题目分析 

        1.多次反转无意义,奇数次的反转等效1次反转;偶数次相当于不反转;

        2.对于当前行黑色块,可以通过对下一行相同位置反转进而实现当前行整体颜色反转

        3.可以通过二进制枚举暴力枚举出第一行所有翻转情况,进而逐步推导下一行翻转情况;

而若到最后一行时仍有黑色块存在,则说明该枚举情况不可行;


#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 20;int m, n;
int ans = 1e7;
int st[N][N];   //起始图例
int turn[N][N]; //翻转图例
int ed[N][N];   //答案图例
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int solve()
{int now[N][N];memcpy(now, st, sizeof st);for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(i != 1 && now[i - 1][j] == 1) turn[i][j] = 1;if(turn[i][j]){now[i][j] ^= 1;for(int k = 0; k < 4; k++){int a = i + dx[k], b = j + dy[k];now[a][b] ^= 1;}}}}for(int j = 1; j <= n; j++) if(now[m][j]) return -1;int temp = 0;for(int i  = 1; i <= m; i++)for(int j = 1; j <= n; j++) temp += now[i][j];return temp;
}int main()
{cin >> m >> n;int flag = 0;for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++) cin >> st[i][j];//二进制枚举所有情况for(int i = 0; i < (1 << n); i++){memset(turn, 0, sizeof turn);for(int j = 0; j < n; j++){if (i & (1 << j)) turn[1][j + 1] = 1;}int temp = solve();if(temp != -1){flag = 1;if(temp < ans){memcpy(ed, turn, sizeof turn);ans = temp;}}}if(!flag) cout << "IMPOSSIBLE" << '\n';else{for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++) cout << ed[i][j] << ' ';cout << '\n';}}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

javaWeb校园二手平台项目

一、系统分析 1.1开发背景 随着全世界互联网技术的不断发展&#xff0c;各种基于互联网技术的网络应用不断涌现,网络技术正在不断的深入人们的生活。人们从Internet上获取信息、享受生活、交流感情、网上工作等。Internet正在迅速改变着人们的生活方式。 经过我国改革开放多年…

中科数安 || 防止公司内部文件资料 \数据外泄,图档透明加密防泄密软件,源代码防泄露系统。

#文件防泄密软件# 中科数安是一家专注于信息安全领域的高科技企业&#xff0c;其提供的防止公司内部文件资料及数据外泄的解决方案主要包括图档透明加密和源代码防泄露系统等核心服务。 中科数安 | 图档、源代码防止外泄系统 PC地址&#xff1a; www.weaem.com 1. 图档透明加…

软考中级 --网络工程师真题试卷 2023下半年

在EIGRP协议中&#xff0c;某个路由器收到了两条路径到达目标网络&#xff0c;路径1的带宽为100Mbps&#xff0c;延迟2ms&#xff0c;路径2的带宽为50Mbps&#xff0c;迟为4ms&#xff0c;如果EIGRP使用带宽和延迟的综合度量标准&#xff0c;那么该路由器选择的最佳路径是(D)。…

记录在项目中引用本地的npm包

1、先把需要的包下载下来&#xff0c;以Photo Sphere Viewer 为引用的npm包、项目以shpereRepo为例子 git clone https://github.com/mistic100/Photo-Sphere-Viewer2、拉下代码后修改之后执行 ./build.sh build.sh #!/usr/bin/env bashyarn run build targetDir"../sh…

java的ArrayList类

ArrayList<E>E是自定义数据类型 ArrayList类&#xff1a; 构造函数&#xff1a; 成员方法&#xff1a; public boolean add(E e)&#xff1a; 将指定元素加到集合末尾 Appends the specified element to the end of this list. public class Array {public static…

Java基础面试复习

一、java基础 1、jdk、jre、jvm的区别 jdk&#xff1a;Java程序开发工具包。 jre&#xff1a;Java程序运行环境。 jvm&#xff1a;Java虚拟机。 2、一个Java源文件中是否可以包含多个类有什么限制 解&#xff1a;可以包含多个类但是只有一个类生命成public并且要和文件名一致 …

抖音小店个人店,个体店,企业店三大店铺类型,优缺点分析!

大家好&#xff0c;我是电商糖果 千万不要盲目的开抖音小店。 因为有三种店铺类型&#xff0c;很多人都会搞不懂它们的优缺点。 选错了&#xff0c;还要关店重新再来一次&#xff0c;既浪费时间&#xff0c;又浪费钱。 这里糖果给大家详细的梳理一下&#xff0c;他们之间的…

Vue2(十一):全局事件总线、消息订阅与发布pubsub、TodoList的编辑功能、$nextTick、过渡与动画

一、全局事件总线 1、思路解析 一种组件间通信的方式&#xff0c;适用于任意组件间通信。通俗理解就是一个定义在所有组件之外的公共x&#xff0c;这个x可以有vm或vc上的同款$on、$off、$emit&#xff0c;也可以让所有组件都访问到。 第一个问题&#xff1a;那怎样添加这个x才…

【SAP2000】碰撞分析 Impact Analysis

碰撞分析 Impact Analysis CSI程序的动力分析功能非常广泛。一个例子是分析两个质量或结构之间碰撞效应的能力。 The possibilities of dynamic analysis with CSI programs are very extensive. An example of this is the ability to analyze the effects of collision bet…

c语言文件操作(下)

目录 1.文件的随机读写1.1 fseek1.2 ftell1.3 rewind 2. 文件结束的判定2.1 文本文件读取结束的判断2.2 二进制文件读取结束的判断 3. 文件缓冲区 1.文件的随机读写 1.1 fseek 根据⽂件指针的位置和偏移量来定位⽂件指针。 函数原型&#xff1a; int fseek (FILE * stream,…

页面router路由设计

Vue命名视图 命名视图 | Vue Router 如果要在 如何要在main区域里使用路由的话&#xff0c;整体区域是Layout&#xff0c;内涵Header和Nav以及Main path: /index,name: index,component: Layout, 若要只修改main区域的话&#xff0c;则取要加上v-if判断&#xff0c;来确实是…

【TB作品】430单片机,单片机串口多功能通信,Proteus仿真

文章目录 题目功能仿真图程序介绍代码、仿真、原理图、PCB 题目 60、单片机串口多功能通信 基本要求: 设计一串口通信程序,波特率38400,通过RS232与PC机通信。 自动循环发送数据串(设计在程序中) 接收并存储和显示该数据串 在发送端定义10个ASCII码键0-9 按键发送单字节,PC机接…

【前端Vue】社交信息头条项目完整笔记第2篇:二、登录注册,准备【附代码文档】

社交媒体-信息头条项目完整开发笔记完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;一、项目初始化使用 Vue CLI 创建项目,加入 Git 版本管理,调整初始目录结构,导入图标素材,引入 Vant 组件库,移动端 REM 适配,关于 , 配置文件,封装请求模块。十、用户关…

【自动化测试教程】Java+Selenium自动化测试环境搭建

本主要介绍以Java为基础&#xff0c;搭建Selenium自动化测试环境&#xff0c;并且实现代码编写的过程。 1.Selenium介绍 Selenium 1.0 包含 core、IDE、RC、grid 四部分&#xff0c;selenium 2.0 则是在两位大牛偶遇相互沟通决定把面向对象结构化&#xff08;OOPP&#xff09…

ADC12123

转换时间的参数一般不太敏感&#xff0c;一般AD转换都很快&#xff0c;如果不需要非常高速的转换频率&#xff0c;那转换时间就可以忽略了。AD转换的时候需要花小段时间&#xff0c; 在AD转换的步骤中&#xff0c;有4步分别是采样、保持、量化、编码&#xff0c;其中采样和保持…

Swift 结构化并发之全局 Actor 趣谈

概览 在 Swift 结构化并发构成的体系中,一个称为“演员”(Actor)的成员扮演了非常重要的角色,它被用来隔离和同步执行中的数据。 除了普通 Actor 以外,还有一个全局“演员”(Global Actor)的概念,它是做什么的?又有什么与众不同的长处呢? 在本篇博文中,您将学到如…

C#学习笔记4:PC串口发送数据

今日继续我的C#学习之路&#xff0c;今日学习制作PC串口发送数据的窗口程序 串口是单片机上位机开发的重点&#xff0c;本文围绕做一个通过PC端串口发送数据的程序进行实践学习&#xff0c; 文章提供源码与解释、整体工程文件 目录 1、控件的选择与摆放&#xff1a; 2、程序设…

Docker搭建LNMP环境实战(02):Win10下安装VMware

实战开始&#xff0c;先安装 VMware 虚拟机。话不多说&#xff0c;上手就干&#xff01; 1、基本环境检查 1.1、本机Bios是否支持虚拟化 进入&#xff1a;任务管理器- 性能&#xff0c;查看“虚拟化”是否启用&#xff0c;如果已启用&#xff0c;则满足要求&#xff0c;如果未…

MyBatis3源码深度解析(二十二)MyBatis拦截器的原理及应用(一)拦截器的实现原理与执行过程

文章目录 前言第九章 MyBatis拦截器的原理及应用9.1 拦截器的实现原理9.1.1 拦截器的注册9.1.2 自定义拦截器9.1.3 拦截器的实现原理9.1.3.1 拦截器支持的类和方法9.1.3.2 Interceptor9.1.3.3 Invocation9.1.3.4 Plugin9.1.3.4.1 getSignatureMap()9.1.3.4.2 getAllInterfaces(…

2024年大模型面试准备(四):大模型面试必会的位置编码(绝对位置编码sinusoidal,旋转位置编码RoPE,以及相对位置编码ALiBi)

节前&#xff0c;我们组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、参加社招和校招面试的同学&#xff0c;针对大模型技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何备战、面试常考点分享等热门话题进行了深入的讨论。 合集在这…