当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
Dialog manager in the fourth chapter: the dialog message loop
PyTorch安装——安装PyTorch前在conda搭建虚拟环境的报错
log4j设置日志的时区
DC-5靶场下载及渗透实战详细过程(DC靶场系列)
ClickHouse—入门
对话框管理器第四章:对话框消息循环
ClickHouse—高级
SM30 表维护视图数据保存前 数据校验事件
我的“眼睛”就是尺!
PyTorch installation - error when building a virtual environment in conda before installing PyTorch
随机推荐
ClickHouse删除表
寄存器(内存访问)
数据库性能系列之索引(中)
compose 位移视图
synchronized原理
ESP8266-Arduino编程实例-LED点阵驱动(基于Max7219)
C# WPF设备监控软件(经典)-上篇
软件测试技术之如何编写测试用例(2)
中断系统需要解决的问题
基于WPF重复造轮子,写一款数据库文档管理工具(一)
flink sql任务变更,在sql里面增加几个字段后,从以前保存的savepoint恢复启动出错。
shell之条件语句(条件测试、if语句,case语句)
v-on指令:为元素绑定事件
对话框管理器第四章:对话框消息循环
v-text指令:设置标签内容
EssilorLuxottica借助Boomi的智能集成平台实现订单处理的现代化
让环境自己说话,论环境自描述的重要性
爆肝22个ES6知识点
【原创】Auto.js get和post 案例
Dynamically modify the title of the navigation bar in uniapp