当前位置:网站首页>2022河南萌新联赛第(四)场:郑州轻工业大学 G - 迷宫
2022河南萌新联赛第(四)场:郑州轻工业大学 G - 迷宫
2022-08-03 03:50:00 【WA_自动机】
G - 迷宫
最短路问题,两两建边,如果目标点为花那么边权为 1 − 1 = 0 1-1=0 1−1=0 ,否则为 1 1 1 固定源点与汇点,最短路的各种算法都可以写,这道题用双端队列比较好写,但是我用的是优先队列。
优先队列
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N = 2010;
char g[N][N];
int f[N][N];
int n,m;
int dx[]={
0,1,0,-1};
int dy[]={
-1,0,1,0};
void bfs()
{
memset(f,0x3f,sizeof f);
f[1][1]=0;
priority_queue<PIII,vector<PIII>,greater<PIII> > Q;
Q.push({
0,{
1,1}});
while(Q.size())
{
PIII t=Q.top();Q.pop();
for(int i=0;i<4;i++)
{
int x=t.second.first+dx[i],y=t.second.second+dy[i];
if(x<1||x>n||y<1||y>m) continue;
if(g[x][y]=='#') continue;
if(f[x][y]!=0x3f3f3f3f) continue;
if(g[x][y]=='.') f[x][y]=min(f[x][y],f[t.second.first][t.second.second]+1);
if(g[x][y]=='*') f[x][y]=min(f[x][y],f[t.second.first][t.second.second]);
Q.push({
f[x][y],{
x,y}});
}
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>(g[i]+1);
bfs();
if(f[n][m]>=0x3f3f3f3f/2) cout<<"-1"<<endl;
else cout<<f[n][m]<<endl;
return 0;
}
双端队列
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2010;
char g[N][N];
int f[N][N];
int n,m;
int dx[]={
0,1,0,-1};
int dy[]={
-1,0,1,0};
void bfs()
{
memset(f,0x3f,sizeof f);
f[1][1]=0;
deque<PII> Q;
Q.push_front({
1,1});
while(!Q.empty())
{
PII t=Q.front();Q.pop_front();
for(int i=0;i<4;i++)
{
int tx=t.first+dx[i],ty=t.second+dy[i];
if(tx<1||tx>n||ty<1||ty>m) continue;
if(g[tx][ty]=='#') continue;
int d=(g[tx][ty]=='.');
if(f[tx][ty]>f[t.first][t.second]+d)
{
f[tx][ty]=f[t.first][t.second]+d;
if(d==0) Q.push_front({
tx,ty});
else Q.push_back({
tx,ty});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>(g[i]+1);
bfs();
if(f[n][m]>=0x3f3f3f3f/2) cout<<"-1"<<endl;
else cout<<f[n][m]<<endl;
return 0;
}
边栏推荐
- flink sql任务变更,在sql里面增加几个字段后,从以前保存的savepoint恢复启动出错。
- Ask next useful SQL server flink - SQL - connector - essentially a CDC - 2
- CyberArk被评为2022年Gartner特权访问管理魔力象限领导者
- uniapp中动态修改导航栏标题
- GD32学习笔记(3)NAND Flash管理
- 金仓数据库 Pro*C 迁移指南(3. KingbaseES Pr*oc 对 Oracle Pro*c 的兼容)
- 9 椭圆曲线密码体制
- Best Practices for Migration from Jincang Database from MySQL to KingbaseES (3. MySQL Database Migration Practice)
- ClickHouse—入门
- EssilorLuxottica借助Boomi的智能集成平台实现订单处理的现代化
猜你喜欢
随机推荐
【STM32】入门(三):按键使用-GPIO端口输出控制
DOM破环和两个实验的复现
Auto.js Pro 编写第一个脚本hello world
七夕??继续肝文章才是正道!!Auto.js 特殊定位控件方法
阿里面试官:聊聊如何格式化Instant
数值类型转换02
ESP8266-Arduino编程实例-MAX6675冷端补偿K热电偶数字转换器驱动
种草一个让程序员男友编程时,记住一辈子的 IDEA 神仙插件!
【笔记】混淆矩阵和ROC曲线
爆肝22个ES6知识点
高等代数_笔记_配方法标准化二次型
DC-6靶场下载及渗透实战详细过程(DC靶场系列)
ClickHouse - Getting Started
compose 位移视图
22 ES6 knowledge points
Smart fitness gesture recognition: PP - TinyPose build AI virtual trainer!
log4j设置日志的时区
Chinese valentine's day??To the liver is the way!!!!!Auto. Js special position control method
OneNote 教程,如何在 OneNote 中设置笔记格式?
Dynamically modify the title of the navigation bar in uniapp