P2802 回家

永远资瓷原创

给个关注吧

 CSDN原力榜排名第12

 

给个关注吧

 P2802 回家

# 回家

## 题目描述

[](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;
}

又加了个火车头优化了一下，想冲个最优解，结果不让用火车头。 

给个关注吧