ZISUOJ 数据结构--队列及其应用

embedded/2024/9/23 10:17:13/

说明:

        基本都是bfs的常见模板题型,思路都很直接,不过后面有两道题很搞心态,它们给的坐标x、y是反的,导致刚开始一直错。题目还是要看仔细,不能先入为主。

题目列表:

问题 A: 围圈报数(完善程序) 

参考题解:

#include<iostream>
#include<queue>
using namespace std;
int n,m,k=1,tmp;
queue<int> arr;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)arr.push(i);// _____(1)____//依次进入队列while(arr.size())// while(_____(2)_____)//判断队列里是否还有人{tmp=arr.front();if(k%m==0)cout<<tmp<<" ";elsearr.push(tmp);// ______(3)______//如果不是第m个人,则重新入队// _____(4)_____//从队列里删除arr.pop();k++;}return 0;
}

问题 B: 围圈报数

参考题解:

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);int n,m,count = 0;cin >> n >> m;std::queue<int> q;for(int i = 1;i<=n;i++) q.push(i);while(q.size()){auto t = q.front();count++;if(count%m==0) {cout << t << ' ';}else {q.push(t);}q.pop();}cout << std::endl;return 0;
}

问题 C: 报数相同次数circle

参考题解:

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);int n;cin >> n;int a,b;cin >> a >> b;std::queue<int> q1,q2;for(int i = 1;i<=a;i++) q1.push(i);for(int i = 1;i<=b;i++) q2.push(i);int count = 0;for(int i = 1;i<=n;i++) {auto t1 = q1.front(),t2 = q2.front();if(t1==t2) count++;q1.push(t1),q2.push(t2);q1.pop(),q2.pop();}cout << count << std::endl;return 0;
}

问题 D: 最小倍数

参考题解:

#include <iostream>
#include <queue>
using std::cin;
using std::cout;
using ll = long long;
ll n,x;
void bfs() {std::queue<ll> q;q.push(1);while(q.size()) {x = q.front();q.pop();if(x%n==0&&x>=n) {cout << x << '\n';return;}q.push(x*10);q.push(x*10+1);}cout << x << '\n';
}
int main() {cin.tie(nullptr)->sync_with_stdio(false);while(cin >> n,n) {bfs();}return 0;
}

问题 E: 迷宫的最短路径

参考题解:

#include <iostream>
#include <queue>
#include <cstring>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);constexpr int N = 1e2+5;int sx = 1,sy = 1,ex = 1,ey = 1;struct node {int x,y,s;}t,t1;char g[N][N];bool vis[N][N];memset(vis,false,sizeof vis);int dx[] = {0,0,-1,1};int dy[] = {-1,1,0,0};std::queue<node> q;int n,m;cin >> n >> m;for(int i = 1;i<=n;i++) {for(int j = 1;j<=m;j++) {cin >> g[i][j];if(g[i][j]=='S') {sx=i,sy=j;}else if(g[i][j]=='G') {ex=i,ey=j;}}}auto bfs = [&]()->void{t.x = sx,t.y = sy,t.s = 0;q.push(t);vis[sx][sy] = true;while(!q.empty()) {t = q.front();q.pop();if(t.x==ex&&t.y==ey) {cout << "The min steps are:" << t.s << "!\n";return;}for(int i = 0;i<4;i++) {int u = t.x+dx[i],v = t.y+dy[i];if(u<1||u>n||v<1||v>m||vis[u][v]||g[u][v]=='#') continue;vis[u][v] = true;t1.x = u,t1.y = v,t1.s = t.s+1;q.push(t1);}}cout << "sorry!\n";};bfs();return 0;
}

问题 F: 象棋中的马之进阶

参考题解:

#include <iostream>
#include <queue>
#include <cstring>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);constexpr int N = 15;struct node {int x,y,s;}t,t1;int dx[] = {-1,1,2,2,1,-1,-2,-2};int dy[] = {2,2,1,-1,-2,-2,-1,1};int sx,sy,ex,ey;bool vis[N][N];memset(vis,false,sizeof vis);cin >> sy >> sx >> ey >> ex;std::queue<node> q;auto bfs = [&]() ->void {t.x = sx,t.y = sy,t.s = 0;vis[sx][sy] = true;q.push(t);while(!q.empty()) {t = q.front();q.pop();if(t.x==ex&&t.y==ey) {cout << t.s << std::endl;return;}for(int i = 0;i<8;i++) {int u = t.x+dx[i],v = t.y+dy[i];if(u<1||u>10||v<1||v>9||vis[u][v]) continue;vis[u][v] = true;t1.x = u,t1.y = v,t1.s = t.s+1;q.push(t1);}}cout << 0 << std::endl;};bfs();return 0;
}

 

问题 G: 迷宫探险

参考题解:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);constexpr int N = 1e2+5;struct node {int x,y,s;bool operator > (const node &W) const {return s > W.s;}}t,t1;char g[N][N];bool vis[N][N];int dx[] = {0,0,-1,1};int dy[] = {-1,1,0,0};int n,sx = 1,sy = 1,ex = 1,ey = 1;std::priority_queue<node,std::vector<node>,std::greater<node>> pq;auto bfs = [&]() ->void {while(!pq.empty()) pq.pop();memset(vis,false,sizeof vis);t.x = sx,t.y = sy,t.s = 0;vis[sx][sy] = true;pq.push(t);while(!pq.empty()) {t = pq.top();pq.pop();if(t.x==ex&&t.y==ey) {cout << t.s << '\n';return;}for(int i = 0;i<4;i++) {int u = t.x+dx[i],v = t.y+dy[i];if(u<1||u>n||v<1||v>n||vis[u][v]||g[u][v]=='#') continue;vis[u][v] = true;int ds = 1;if(g[u][v]!='.') ds += int(g[u][v]^48);t1.x = u,t1.y = v,t1.s = t.s+ds;pq.push(t1);}}cout << -1 << '\n';};while(cin >> n) {ex = n,ey = n;for(int i = 1;i<=n;i++) {for(int j = 1;j<=n;j++) {cin >> g[i][j];}}bfs();}return 0;
}

问题 H: 迷宫

 

参考题解:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using std::cin;
using std::cout;
int main() {cin.tie(nullptr)->sync_with_stdio(false);constexpr int N = 1e2+5;struct node {int x,y,s;}t,t1;char g[N][N];bool vis[N][N];int dx[] = {0,0,-1,1};int dy[] = {-1,1,0,0};int sx,sy,ex,ey,k,n,m;std::queue<node> q;auto bfs = [&]()->void {memset(vis,false,sizeof vis);while(!q.empty()) q.pop();t.x = sx,t.y = sy,t.s = -1;vis[sx][sy] = true;q.push(t);while(!q.empty()) {t = q.front();q.pop();if(t.x==ex&&t.y==ey&&t.s<=k) {cout << "yes\n";return;}for(int i = 0;i<4;i++) {t1.x = t.x+dx[i],t1.y = t.y+dy[i];int &u = t1.x,&v = t1.y;while(u>=1&&u<=n&&v>=1&&v<=m&&g[u][v]=='.') {if(!vis[u][v]) {t1.s=t.s+1;vis[u][v] = true;q.push(t1);}u+=dx[i],v+=dy[i];}}}cout << "no\n";};int T = 1;cin >> T;while(T--) {cin >> n >> m;for(int i = 1;i<=n;i++) {for(int j = 1;j<=m;j++) {cin >> g[i][j];}}cin >> k >> sy >> sx >> ey >> ex;bfs();}return 0;
}


http://www.ppmy.cn/embedded/22851.html

相关文章

特征提取(Feature Extraction)应用场景笔记(二)

让我们以一个交通管理系统为例&#xff0c;说明如何基于统计特征、频域特征和时域特征设计数据表示。 假设我们有大量的交通流量数据&#xff0c;包括车辆的速度、密度、道路拥堵情况等指标。我们的任务是让强化学习代理学习交通流量模式&#xff0c;并根据数据做出智能的交通信…

408计算机组成原理知识点——第五章 中央处理器

文章目录 CPU的功能和基本结构CPU的功能运算器和控制器的功能运算器的基本结构专用数据通路方式CPU内部单总线方式运算器的基本结构 控制器的基本结构CPU的基本结构 指令执行过程指令周期指令周期流程指令周期的数据流取指周期间址周期执行周期中断周期 指令的执行方案 数据通路…

Milvus Cloud 向量数据库Reranker成本比较和使用场景

成本比较:向量检索 v.s. Cross-encoder Reranker v.s. 大模型生成 虽然 Reranker 的使用成本远高于单纯使用向量检索的成本,但它仍然比使用 LLM 为同等数量文档生成答案的成本要低。在 RAG 架构中,Reranker 可以筛选向量搜索的初步结果,丢弃掉与查询相关性低的文档,从而有…

Spark调优-解决job任务运行超时或者慢的问题

1 三个参数各自的作用(都配置在spark-default.conf文件中) 1.1 spark.shuffle.io.connectionTimeout (默认值是120s) 这个参数设置了在 shuffle 过程中,当一个 reduce 任务尝试从 map 任务读取数据时,建立连接的超时时间。如果在这个时间内连接没有成功建立,那么 redu…

python利用urllib和xpath爬取并保存图片

概要 在网络时代&#xff0c;图片是信息传递的重要形式之一&#xff0c;而Python作为一种多用途的编程语言&#xff0c;可以用来编写爬虫从网页上获取图片&#xff0c;并保存到本地。本文将介绍如何使用Python爬虫实现这一功能&#xff0c;并探讨一些进阶技巧。 实现 &#x…

深度学习的炼金术:转化数据为黄金的秘密

深度学习的炼金术&#xff1a;转化数据为黄金的秘密 1 引言 在现代深度学习的壮阔疆域中&#xff0c;数据是王冠上耀眼的宝石&#xff0c;而性能优化则是锻造这顶王冠的炼金术。这份融合了数据和算法魔力的艺术&#xff0c;不仅仅依赖于强大的计算资源和复杂的网络结构&#x…

Mysql(数据库)知识详解【6】~{锁,架构}

数据库锁和架构是两个不同的概念&#xff0c;但它们都与数据库管理系统&#xff08;DBMS&#xff09;的性能和并发控制有关。 数据库锁&#xff1a; 数据库锁是一种同步机制&#xff0c;用于控制多个事务对共享资源的访问。锁可以确保数据的一致性和完整性&#xff0c;防止多个…

vscode 如何断点调试ros1工程

在vscode中断点调试ros1工程主要分为以下几步&#xff1a; 1. 第一步就是修改cmakelist.txt&#xff0c;到调试模式。 将CMAKE_BUILD_TYPE原来对应的代码注释掉&#xff0c;原来的一般都不是调试模式。加上下面一行代码&#xff0c;意思是设置调试模式。 # 断点调试 SET(CMAK…