(简单bfs)百练4116:拯救行动

news/2025/2/15 6:19:31/

传送门:百练4116:拯救行动

题解:因为骑士杀死守卫会耗费时间,所以要用优先队列来维护步数。

收获:学会了无参构造方法的使用。

代码1:注意用无参构造方法的话,就不能再构造结构体类型的变量啦,例如,Maze tmp;这样的就不可以。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=210;
char mp[maxn][maxn];
int n,m,x1,y1;
int dir[4][2]={-1,0,1,0,0,-1,0,1},vis[maxn][maxn];   //上下左右struct Maze{int x,y;int step;bool operator<(const Maze &m)const{return step>m.step;}Maze(int x,int y,int s): x(x),y(y),step(s){}
};int bfs(int x,int y){priority_queue<Maze > pq;pq.push(Maze(x,y,0));while(!pq.empty()){int tmp_x=pq.top().x;int tmp_y=pq.top().y;int tmp_step=pq.top().step;pq.pop();//cout<<"tmp.x="<<tmp.x<<",tmp.y="<<tmp.y<<",tmp.step="<<tmp.step<<",mp[tmp.x][tmp.y]="<<mp[tmp.x][tmp.y]<<endl;//if(mp[tmp.x][tmp.y]=='a') return tmp.step;for(int i=0;i<4;i++){int dx=tmp_x+dir[i][0];int dy=tmp_y+dir[i][1];if(dx<0||dy<0||dx>=n||dy>=m) continue;if(!vis[dx][dy]){vis[dx][dy]=1;if(mp[dx][dy]=='@'){pq.push(Maze(dx,dy,tmp_step+1));}else if(mp[dx][dy]=='x'){pq.push(Maze(dx,dy,tmp_step+2));}else if(mp[dx][dy]=='a'){return tmp_step+1;}}}}return -1;
}int main(){int s;scanf("%d",&s);while(s--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",mp[i]);}int x=-1,y;for(int i=0;i<n;i++){if(x!=-1) break;for(int j=0;j<m;j++){if(mp[i][j]=='r'){x=i;y=j;}}}memset(vis,0,sizeof(vis));int ans=bfs(x,y);if(ans==-1) printf("Impossible\n");else printf("%d\n",ans);}return 0;
}

代码2:不用无参构造方法,

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=210;
char mp[maxn][maxn];
int n,m,x1,y1;
int dir[4][2]={-1,0,1,0,0,-1,0,1},vis[maxn][maxn];   //上下左右struct Maze{int step;int x,y;bool operator<(const Maze &m)const{return step>m.step;}
}tmp,nxt;int bfs(int x,int y){priority_queue<Maze > pq;tmp.x=x;tmp.y=y;tmp.step=0;pq.push(tmp);while(!pq.empty()){tmp=pq.top();pq.pop();//cout<<"tmp.x="<<tmp.x<<",tmp.y="<<tmp.y<<",tmp.step="<<tmp.step<<",mp[tmp.x][tmp.y]="<<mp[tmp.x][tmp.y]<<endl;//if(mp[tmp.x][tmp.y]=='a') return tmp.step;for(int i=0;i<4;i++){int dx=tmp.x+dir[i][0];int dy=tmp.y+dir[i][1];if(dx<0||dy<0||dx>=n||dy>=m) continue;nxt.x=dx;nxt.y=dy;if(!vis[dx][dy]){vis[dx][dy]=1;if(mp[dx][dy]=='@'){nxt.step=tmp.step+1;//cout<<"nxt.x="<<nxt.x<<",nxt.y="<<nxt.y<<",nxt.step="<<nxt.step<<",mp[nxt.x][nxt.y]="<<mp[nxt.x][nxt.y]<<endl;pq.push(nxt);}else if(mp[dx][dy]=='x'){nxt.step=tmp.step+2;//cout<<"nxt.x="<<nxt.x<<",nxt.y="<<nxt.y<<",nxt.step="<<nxt.step<<",mp[nxt.x][nxt.y]="<<mp[nxt.x][nxt.y]<<endl;pq.push(nxt);}else if(mp[dx][dy]=='a'){return tmp.step+1;}}}}return -1;
}int main(){int s;scanf("%d",&s);while(s--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%s",mp[i]);}int x=-1,y;for(int i=0;i<n;i++){if(x!=-1) break;for(int j=0;j<m;j++){if(mp[i][j]=='r'){x=i;y=j;}}}memset(vis,0,sizeof(vis));int ans=bfs(x,y);if(ans==-1) printf("Impossible\n");else printf("%d\n",ans);}return 0;
}

 


http://www.ppmy.cn/news/202554.html

相关文章

OpenJ_Bailian - 4116拯救行动(bfs+优先队列)

4116:拯救行动 查看提交统计提示提问 总时间限制: 1000ms 内存限制: 65536kB 描述 公主被恶人抓走&#xff0c;被关押在牢房的某个地方。牢房用N*M (N, M < 200)的矩阵来表示。矩阵中的每项可以代表道路&#xff08;&#xff09;、墙壁&#xff08;#&#xff09;、和…

安装 MySQL 8 如何在生产环境中

文章结构 安装生产环境安装 MySQLDocker 安装 MySQL MySQL 完全卸载&#xff08;危险操作&#xff09;相关资源网址 安装 官方文档 MySQL 8.0 描述的是 最新版本最新版本的特性&#xff0c;可能跟你安装版本的特性有’小许差异’!!!&#xff0c;小的差异点很多&#xff0c;不列…

Unity制作二次元卡通渲染角色材质

Unity制作二次元材质角色 大家好&#xff0c;我是阿赵。接下来准备开一个系列&#xff0c;讲一下二次元卡通角色的渲染。   先来看看成品&#xff0c;我从网上下载了著名游戏《罪恶装备》里面的一个角色模型。在没有做材质之前&#xff0c;把贴图赋予上去&#xff0c;给一个U…

【生成数据】绘制简单的折线图

使用scatter绘制散点图并设置其样式 plt.scatter(2, 4, s200)#设置图表标题并给坐标轴加上标签 plt.title("Square Number", fontsize24) plt.xlabel("Value", fontsize14) plt.ylabel("Square of Value", fontsize14)#设置刻度标记的大小 plt.…

Linux下parted分区超过2TB硬盘-分区格式化

1、parted 设备名进入分区 parted /dev/vdb 2、输入print打印列出当前分区设备的磁盘容量大小 3、设置磁盘分区为gpt模 mklabel gpt 然后点击YES继续(提示磁盘的数据可能会丢失是否继续&#xff09;提示警告&#xff0c;忽略继续即可输入 i 或者 ignore 4、设置磁盘文件系统格式…

计算机硬盘安装的两大,电脑硬盘装2个1TB的硬盘好还是1个2TB的硬盘好?

总体来说1个2tb的硬盘好&#xff01; 从功耗来说&#xff1a; 1个2tb的硬盘比2个1tb的硬盘功耗要低得多&#xff0c;假如一个1tb硬盘的功耗是50w&#xff0c;两个就是100w&#xff0c;那么如若1个2tb的硬盘是80w的话&#xff0c;1个2tb的硬盘占优势。 从储存速度来说&#xff1…

计算机移动硬盘的一般作用,2t移动硬盘分区是否必要?它的功能和意义是什么?...

gaofan0905 通过 是否需要对移动硬盘进行分区&#xff1f;硬盘主要用于存储事物&#xff0c;就像USB闪存驱动器一样. 如果要分类&#xff0c;只需创建几个文件夹即可. 就个人而言&#xff0c;不需要分区~~~: 我想了解更多详细信息&#xff0c;谢谢&#xff01;答: 分区的作用与…

Linux系统安装大于2TB硬盘

关于Linux系统无法安装大于2TB硬盘的解决方法 1&#xff0e;在系统安装界面 在这个界面按ctrlaltF2 调出命令行修改硬盘类型为GPT就可以安装了 parted mklabel gpt gpt修改完之后将系统重启&#xff0c;然后进行安装。&#xff08;CrtlaltF6 调用图形界面&#xff0c;ctrlal…