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

news/2024/4/19 2:29:25

传送门:百练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…

linux下大于2TB硬盘parted 分区

linux下大于2TB硬盘格式化及挂载,linux下大于2T的分区方法&#xff0c;linux GPT分区表 管理 自动挂载分区 2012-03-12 16:59:11| 分类&#xff1a; LINUX|举报|字号 订阅 先介绍两种分区表&#xff1a; MBR分区表&#xff1a;&#xff08;MBR含义&#xff1a;主引导记录&am…

Linux7识别大硬盘驱动,Linux系统无法识别2TB以上硬盘

MBR分区表:(MBR含义:主引导记录) 所支持的最大卷:2T (T; terabytes,1TB=1024GB) 对分区的设限:最多4个主分区或3个主分区加一个扩展分区。 GPT分区表:(GPT含义:GUID分区表) 支持最大卷:18EB,(E:exabytes,1EB=1024TB) 每个磁盘最多支持128个分区 使用 parted 建立大小超…

Ubuntu 2TB以上硬盘的挂载

功能:Ubuntu 使用2TB以上的硬盘挂载 硬盘本来是dos格式&#xff0c;在这种格式下最大只能分配2TB。 1.sudo fdisk -l /dev/sdb 可以看到/dev/sdb的格式为dos 2.使用sudo parted /dev/sdb 命令 输入mklable 后输入gpt,然后退出 3.使用sudo blkid /dev/sdb 可以查看磁盘类型…

希捷发布世界最薄、最快2TB硬盘:7毫米

希捷今天宣布推出全球首款7毫米厚度的2TB容量硬盘&#xff0c;同时也是业内重量最轻、速度最快、能耗最高的7毫米硬盘。 这种新的2.5寸硬盘采用SMR叠瓦式磁记录存储&#xff0c;单碟容量1TB&#xff0c;总容量有2TB(双碟)、1TB(单碟)两种。接口SATA 6Gbps&#xff0c;缓存容量1…

Centos用parted分区超过2TB硬盘-分区格式化

1、问题描述 1)、问题一 CentOS 6.x 在格式化大于16TB的ext4分区时,会提示如下错误: mke2fs 1.41.12 (17-May-2010) mkfs.ext4: Size of device /dev/sda1 too big to be expressed in 32 bits using a blocksize of 4096. 2)、问题二 CentOS 6.x 无法使用fdisk分区大于2…

CentOS parted分割大于2TB硬盘的performance问题处理

在CentOS下&#xff0c;通常采用parted工具对超过2TB容量的硬盘进行分区工作&#xff1b;但在实际操作中执行 mkpart 指令将整个空间分给一个区时&#xff0c;通常会出现一个如下的 warning信息&#xff1a; 之前我一直都是直接输入I&#xff0c;选择Ignore忽略了这个警告继续分…

Centos怎么用parted分区超过2TB硬盘-分区格式化

Parted分区 1 通过输入parted 设备名进入分区命令行模式如下图 2 通过parint打印列出当前分区设备的磁盘容量大小&#xff0c;如下图12.9tb 3 设置磁盘分区为gpt模式&#xff0c; mklabel gpt 然后点击YEs继续(提示磁盘的数据可能会丢失是否继续&#xff09; 4 提示下面警告&a…

冰点还原 7.20.20.3398 For Win2003 支持2TB硬盘版下载,附KEY和修改方法

冰点还原 7.20.20.3398 For Win2003 支持2TB硬盘版下载&#xff0c;附KEY和修改方法 相关搜索: 百度一下, 修改器, 版下载, 朋友 首先说明&#xff0c;我就是WINZHENG的XYBOYS&#xff0c;7.20版本的WIN2003修改点和支持2TB大硬盘的修改点都按先前网上某前辈所写的调试过程…

WD强势出击 推出全球业界首款2TB硬盘

西部数据 (WD) 今天推出了其首款2TB硬盘&#xff0c;这也是目前全球业界容量最高的硬盘。这款3.5英寸硬盘是WD Caviar Green系列家族的新成员&#xff0c;通过实现低发热量、低噪音的运转&#xff0c;从而更专注于绿色环保。它采用了WD在业界领先的单碟容量500GB技术 (存储密度…

怎么在linux(centos、redhat、ubuntu)中挂载超过2tb硬盘

此次以centos为例&#xff1a; 还是直接以图示的方式进行说明&#xff01; 在linux系统中超过2tb容量的硬盘需要改成gpt格式&#xff0c;以parted 工具进行格式化挂载才能使用。2tb以下用fdisk完全没问题。下面是步骤和图文&#xff1a; 首先需要lsblk 查看下新盘盘符&#xff…

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

Centos怎么用parted分区超过2TB硬盘-分区格式化 安装好parted命令之后&#xff0c;通过fdisk -l查看硬盘所在分区名称 关于lvm分区教程可以参考&#xff1a; 图形界面&#xff1a;jingyan.baidu.com/season/39077 命令行LVM&#xff1b;jingyan.baidu.com/season/38880 工具…

月嫂提前离开雇主不舍偷偷抹泪

请珍惜你们身边的月嫂&#xff0c;善待她们&#xff0c;感激她们。 因为每一位月嫂都是独一无二的&#xff0c;无法替代的。 愿每一个宝宝都能遇到最好的月嫂&#xff0c;愿每一个月嫂都能被温柔以待。 近日&#xff0c;在江苏南京&#xff0c;有一位月嫂因为提前离开雇主家而流…