当前位置:网站首页>P2802 回家
P2802 回家
2022-07-06 05:32:00 【暴揍键盘的程序猿】
永远资瓷原创
CSDN原力榜排名第12
# 回家
## 题目描述
[](https://paste.ubuntu.com/p/DSg5bzrrjs/)
小 H 在一个划分成了 $n \times m$ 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小 H 不可以静止不动), 但不能离开封锁线,否则就被打死了。 刚开始时他有满血 $6$ 点,每移动一格他要消耗 $1$ 点血量。一旦小 H 的血量降到 $0$, 他将死去。 他可以沿路通过拾取鼠标(什么鬼。。。)来补满血量。只要他走到有鼠标的格子,他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满,所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去, 他也不能通过拾取鼠标补满 HP。 即使在家门口死去, 他也不能算完成任务回到家中。
地图上有五种格子:
`0`:障碍物。
`1`:空地, 小 H 可以自由行走。
`2`:小 H 出发点, 也是一片空地。
`3`:小 H 的家。
`4`:有鼠标在上面的空地。
小 H 能否安全回家?如果能, 最短需要多长时间呢?
## 输入格式
第一行两个整数 $n,m$, 表示地图的大小为 $n \times m$。
下面 $n$ 行, 每行 $m$ 个数字来描述地图。
## 输出格式
一行, 若小 H 不能回家, 输出 `-1`,否则输出他回家所需最短时间。
## 样例 #1
### 样例输入 #1
```
3 3
2 1 1
1 1 0
1 1 3
```
### 样例输出 #1
```
4
```
## 提示
对于所有数据,$1 \le n,m \le 9$。
2021.9.2 增添一组 hack 数据 by @囧仙
【一堆64分代码】
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=9;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int map[N][N],dx[4][2]/*=*/{0,1,0,-1,1,0,-1,0},a[N][N],n,m,x,y;
bool flag=true;
struct node
{
int n,m,x,y;
}z,p;
queue<node>q;
signed main()
{
n=fread(),m=fread();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
map[i][j]=fread();
if(map[i][j]==2)x=i,y=j;//记录出发位置
}
q.push((node){x,y,0,6}),a[x][y]=6;//初始位置设置其a值
while(!q.empty() and flag)//直到完全失败或成功
{
z=q.front()/*取队列最前面的节点*/,q.pop();
if(z.y==1)continue;//如果血量为1,则继续
for(int i=0;i<4 and flag;i++)//四个方向
{
if(map[z.n+dx[i][0]][z.m+dx[i][1]])//如果可以到达
if(a[z.n+dx[i][0]][z.m+dx[i][1]]<z.y-1)//如果血量更大
{
p.n=z.n+dx[i][0],p.m=z.m+dx[i][1],p.x=z.x+1/*更新新的节点*/,p.y=map[z.n][z.m]==4?6:z.y-1/*如果下一个节点是有鼠标的,那么有变成6*/,a[p.n][p.m]=z.y-1;//更新a
if(map[p.n][p.m]==3)flag=false;//如果任务完成,那么flag更新
q.push(p);
}
}
}
if(flag)printf("-1");
else fwrite(p.x);
return 0;
}
发现不加等号不会CE,就勇了一波。
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=9;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int map[N][N],dx[4][2]={0,1,0,-1,1,0,-1,0},a[N][N],n,m,x,y;
bool flag=true;
struct node
{
int n,m,x,y;
}z,p;
queue<node>q;
signed main()
{
n=fread(),m=fread();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
map[i][j]=fread();
if(map[i][j]==2)x=i,y=j;//记录出发位置
}
q.push((node){x,y,0,6}),a[x][y]=6;//初始位置设置其a值
while(!q.empty() and flag)//直到完全失败或成功
{
z=q.front()/*取队列最前面的节点*/,q.pop();
if(z.y==1)continue;//如果血量为1,则继续
for(int i=0;i<4 and flag;i++)//四个方向
{
if(map[z.n+dx[i][0]][z.m+dx[i][1]])//如果可以到达
if(a[z.n+dx[i][0]][z.m+dx[i][1]]<z.y-1)//如果血量更大
{
p.n=z.n+dx[i][0],p.m=z.m+dx[i][1],p.x=z.x+1/*更新新的节点*/,p.y=map[z.n][z.m]==4?6:z.y-1/*如果下一个节点是有鼠标的,那么有变成6*/,a[p.n][p.m]=z.y-1;//更新a
if(map[p.n][p.m]==3)flag=false;//如果任务完成,那么flag更新
q.push(p);
}
}
}
if(flag)printf("-1");
else fwrite(p.x);
return 0;
}
以为是等号的问题,结果不是。
【CE代码】
#include<cstdio>
#include<iostream>
#include<queue>
const int N=9;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int n,m,v[N][N],g[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},s,s1;
struct node
{
int x,y,s,b;
node(){}
node(int x1,int yy1,int s1,int b1)
{
x=x1,y=yy1,s=s1,b=b1;
}
};
queue<node>q;
signed main()
{
n=fread(),m=fread();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
g[i][j]=fread();
if(g[i][j]==2)s=i,s1=j;
}
v[s][s1]=6,q.push(node(s,s1,0,6));
while(!q.empty())
{
node t=q.front();
q.pop();
int x=t.x,y=t.y,s=t.s,b=t.b;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],yy1=y+dy[i],b1=b-1;
if(g[x1][yy1]==0 or b1==0)continue;
if(g[x1][yy1]==3)
{
fwrite(s+1);
return 0;
}
if(g[x1][yy1]==4)b1=6;
if(v[x1][yy1]>=b1)continue;
q.push(node(x1,yy1,s+1,b1)),v[x1][yy1]=b1;
}
}
printf("-1");
return 0;
}
忘打
using namespace std;
了
【80分代码】
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=9;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int n,m,v[N][N],g[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},s,s1;
struct node
{
int x,y,s,b;
node(){}
node(int x1,int yy1,int s1,int b1)
{
x=x1,y=yy1,s=s1,b=b1;
}
};
queue<node>q;
signed main()
{
n=fread(),m=fread();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
g[i][j]=fread();
if(g[i][j]==2)s=i,s1=j;
}
v[s][s1]=6,q.push(node(s,s1,0,6));
while(!q.empty())
{
node t=q.front();
q.pop();
int x=t.x,y=t.y,s=t.s,b=t.b;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],yy1=y+dy[i],b1=b-1;
if(g[x1][yy1]==0 or b1==0)continue;
if(g[x1][yy1]==3)
{
fwrite(s+1);
return 0;
}
if(g[x1][yy1]==4)b1=6;
if(v[x1][yy1]>=b1)continue;
q.push(node(x1,yy1,s+1,b1)),v[x1][yy1]=b1;
}
}
printf("-1");
return 0;
}
数组开小了。
【AC代码】
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int N=20;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int n,m,v[N][N],g[N][N],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},s,s1;
struct node
{
int x,y,s,b;
node(){}
node(int x1,int yy1,int s1,int b1)
{
x=x1,y=yy1,s=s1,b=b1;
}
};
queue<node>q;
signed main()
{
n=fread(),m=fread();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
g[i][j]=fread();
if(g[i][j]==2)s=i,s1=j;
}
v[s][s1]=6,q.push(node(s,s1,0,6));
while(!q.empty())
{
node t=q.front();
q.pop();
int x=t.x,y=t.y,s=t.s,b=t.b;
for(int i=0;i<4;i++)
{
int x1=x+dx[i],yy1=y+dy[i],b1=b-1;
if(g[x1][yy1]==0 or b1==0)continue;
if(g[x1][yy1]==3)
{
fwrite(s+1);
return 0;
}
if(g[x1][yy1]==4)b1=6;
if(v[x1][yy1]>=b1)continue;
q.push(node(x1,yy1,s+1,b1)),v[x1][yy1]=b1;
}
}
printf("-1");
return 0;
}
又加了个火车头优化了一下,想冲个最优解,结果不让用火车头。
边栏推荐
- Mongodb basic knowledge summary
- Please wait while Jenkins is getting ready to work
- Mysql高级篇学习总结9:创建索引、删除索引、降序索引、隐藏索引
- 【LeetCode】18、四数之和
- flutter 实现一个有加载动画的按钮(loadingButton)
- 05. 博客项目之安全
- Tetris
- Force buckle 1189 Maximum number of "balloons"
- Game push image / table /cv/nlp, multi-threaded start
- Modbus protocol communication exception
猜你喜欢
注释、接续、转义等符号
Vulhub vulnerability recurrence 67_ Supervisor
Easy to understand I2C protocol
02. 开发博客项目之数据存储
用StopWatch 统计代码耗时
05. 博客项目之安全
pix2pix:使用条件对抗网络的图像到图像转换
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Configuration file converted from Excel to Lua
29io stream, byte output stream continue write line feed
随机推荐
How to get list length
Closure, decorator
59. Spiral matrix
PDK工艺库安装-CSMC
[force buckle]43 String multiplication
Graduation design game mall
Can the feelings of Xi'an version of "Coca Cola" and Bingfeng beverage rush for IPO continue?
初识CDN
Quantitative description of ANC noise reduction
注释、接续、转义等符号
Improve jpopup to realize dynamic control disable
图数据库ONgDB Release v-1.0.3
05. Security of blog project
[leetcode daily question] number of enclaves
用StopWatch 统计代码耗时
Vulhub vulnerability recurrence 72_ uWSGI
Using stopwatch to count code time
Pointer classic written test questions
Vulhub vulnerability recurrence 67_ Supervisor
pix2pix:使用条件对抗网络的图像到图像转换