P2802 go home

Forever Zici original

Pay attention to it

 CSDN Force list Ranking the first 12

 

Pay attention to it

 P2802 get home

# 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 . 

Pay attention to it

 

#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 . 

Pay attention to it

 【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;

  了

Pay attention to it

 【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 . 

Pay attention to it

 【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 . 

Pay attention to it