当前位置:网站首页>P2802 go home
P2802 go home
2022-07-06 05:42:00 【A program ape who beats the keyboard violently】
Forever Zici original
CSDN Force list Ranking the first 12
# get home
## Title Description
[](https://paste.ubuntu.com/p/DSg5bzrrjs/)
Small H It's divided into $n \times m$ A rectangular cordon with two squares . Every time he can move one space up, down, left and right ( Of course small H Don't stand still ), But you can't leave the blockade , Or you'll be killed . At first he was full of blood $6$ spot , Each move consumes $1$ Point blood volume . Once small H Your blood volume is reduced to $0$, He will die . He can pick up the mouse along the road ( What the hell? ...) To fill up the blood volume . As long as he walks to the grid with a mouse , He doesn't need any time to pick up . The mouse on the grid can fill up in an instant , So every time I pass through this grid, there is a mouse . Even if you die in a grid with a mouse , He can't fill it up by picking up the mouse HP. Even if you die at home , He can't finish the task and come home .
There are five grids on the map :
`0`: obstacle .
`1`: clearing , Small H Can walk freely .
`2`: Small H starting point , It's also an open space .
`3`: Small H s home .
`4`: There is a mouse in the open space above .
Small H Can you go home safely ? If you can , How long is the shortest time ?
## Input format
The first line has two integers $n,m$, Indicates that the size of the map is $n \times m$.
below $n$ That's ok , Each row $m$ A number to describe the map .
## Output format
a line , If small H Can't go home , Output `-1`, Otherwise, the shortest time he needs to go home .
## Examples #1
### The sample input #1
```
3 3
2 1 1
1 1 0
1 1 3
```
### Sample output #1
```
4
```
## Tips
For all the data ,$1 \le n,m \le 9$.
2021.9.2 Add a group hack data by @ Embarrassing Fairy
【 a pile 64 Code division 】
#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;// Record the starting position
}
q.push((node){x,y,0,6}),a[x][y]=6;// The initial position sets its a value
while(!q.empty() and flag)// Until complete failure or success
{
z=q.front()/* Take the node at the front of the queue */,q.pop();
if(z.y==1)continue;// If the blood volume is 1, Continued to
for(int i=0;i<4 and flag;i++)// Four directions
{
if(map[z.n+dx[i][0]][z.m+dx[i][1]])// If you can get there
if(a[z.n+dx[i][0]][z.m+dx[i][1]]<z.y-1)// If you have more blood
{
p.n=z.n+dx[i][0],p.m=z.m+dx[i][1],p.x=z.x+1/* Update new nodes */,p.y=map[z.n][z.m]==4?6:z.y-1/* If the next node has a mouse , Then it has become 6*/,a[p.n][p.m]=z.y-1;// to update a
if(map[p.n][p.m]==3)flag=false;// If the task is completed , that flag to update
q.push(p);
}
}
}
if(flag)printf("-1");
else fwrite(p.x);
return 0;
}
It is found that not adding an equal sign will not CE, Just brave a wave .
#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;// Record the starting position
}
q.push((node){x,y,0,6}),a[x][y]=6;// The initial position sets its a value
while(!q.empty() and flag)// Until complete failure or success
{
z=q.front()/* Take the node at the front of the queue */,q.pop();
if(z.y==1)continue;// If the blood volume is 1, Continued to
for(int i=0;i<4 and flag;i++)// Four directions
{
if(map[z.n+dx[i][0]][z.m+dx[i][1]])// If you can get there
if(a[z.n+dx[i][0]][z.m+dx[i][1]]<z.y-1)// If you have more blood
{
p.n=z.n+dx[i][0],p.m=z.m+dx[i][1],p.x=z.x+1/* Update new nodes */,p.y=map[z.n][z.m]==4?6:z.y-1/* If the next node has a mouse , Then it has become 6*/,a[p.n][p.m]=z.y-1;// to update a
if(map[p.n][p.m]==3)flag=false;// If the task is completed , that flag to update
q.push(p);
}
}
}
if(flag)printf("-1");
else fwrite(p.x);
return 0;
}
Think it's an equal sign problem , It didn't turn out to be .
【CE Code 】
#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;
}
Forget to type
using namespace std;
了
【80 Code division 】
#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;
}
The array is down .
【AC Code 】
#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;
}
Another locomotive is added to optimize , Want to rush for an optimal solution , As a result, the locomotive was not allowed .
边栏推荐
- Self built DNS server, the client opens the web page slowly, the solution
- LeetCode_ String inversion_ Simple_ 557. Reverse word III in string
- Huawei od computer test question 2
- B站刘二大人-Softmx分类器及MNIST实现-Lecture 9
- UCF (summer team competition II)
- HAC集群修改管理员用户密码
- [cloud native] 3.1 kubernetes platform installation kubespher
- LeetCode_字符串反转_简单_557. 反转字符串中的单词 III
- 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
- ArcGIS application foundation 4 thematic map making
猜你喜欢
Redis message queue
ARTS Week 25
B站刘二大人-Softmx分类器及MNIST实现-Lecture 9
Zoom and pan image in Photoshop 2022
[SQL Server fast track] - authentication and establishment and management of user accounts
26file filter anonymous inner class and lambda optimization
- [email protected] raspberry pie"/>
[email protected] raspberry pie
注释、接续、转义等符号
B站刘二大人-数据集及数据加载 Lecture 8
应用安全系列之三十七:日志注入
随机推荐
How to use PHP string query function
C进阶-数据的存储(上)
What is independent IP and how about independent IP host?
2022 half year summary
Garbage collector with serial, throughput priority and response time priority
Download, install and use NVM of node, and related use of node and NRM
[detailed explanation of Huawei machine test] statistics of shooting competition results
Embedded interview questions (IV. common algorithms)
Web Security (V) what is a session? Why do I need a session?
Vulhub vulnerability recurrence 71_ Unomi
05. Security of blog project
B站刘二大人-多元逻辑回归 Lecture 7
[SQL Server fast track] - authentication and establishment and management of user accounts
【torch】|torch.nn.utils.clip_grad_norm_
HAC cluster modifying administrator user password
Summary of deep learning tuning tricks
Pytorch代码注意的细节,容易敲错的地方
LeetCode_ String inversion_ Simple_ 557. Reverse word III in string
Vulhub vulnerability recurrence 69_ Tiki Wiki
How can large websites choose better virtual machine service providers?