请问为什么用-1就是错的,用无穷大就是对的,百思不得解佬们
查看原帖
请问为什么用-1就是错的,用无穷大就是对的,百思不得解佬们
1034242
RingTouSou楼主2023/10/24 22:29

这是无穷大的代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N=310;
#define x first
#define y second

int m;
int dist[N][N];
int fire[N][N];
PII q[N*N];

int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

int bfs()
{
	q[0]={0,0};
	dist[0][0] = 0;
	int hh=0,tt=0;
	
	while(hh<=tt)
	{
		auto t=q[hh++];
	
	    for(int i=0;i<4;i++)
	    {
		int a=t.x+dx[i];
		int b=t.y+dy[i];
		
		if(a<0||b<0)	continue;
		if(dist[a][b])    continue;
		if(dist[t.x][t.y]+1>=fire[a][b]) 	continue;
		
		
		dist[a][b] = dist[t.x][t.y] + 1;
		q[++tt]={a,b};
		
		if(fire[a][b]>1e9)	return dist[a][b];
	}
	}
	return -1;
}
int main()
{
	memset(fire,0x3f,sizeof fire);
	cin>>m;
	while(m--)
	{
		int x1,y1,t;
		cin>>x1>>y1>>t;
	    fire[x1][y1]=min(t,fire[x1][y1]);
		for(int i=0;i<4;i++)
		{
			int a = x1 + dx[i];
			int b = y1 + dy[i];
			if(a<0||a>301||b<0||b>301)
			{
				continue;
			 } 
			fire[a][b]=min(t,fire[a][b]);
		} 
	}
	int k=bfs();
	cout<<k;
	return 0;
}

这是-1的代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef pair<int, int> PII;

const int N=310;
#define x first
#define y second

int m;
int dist[N][N];
int fire[N][N];
PII q[N*N];

int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

int bfs()
{
	q[0]={0,0};
	dist[0][0] = 0;
	int hh=0,tt=0;
	
	while(hh<=tt)
	{
		auto t=q[hh++];
	
	    for(int i=0;i<4;i++)
	    {
		int a=t.x+dx[i];
		int b=t.y+dy[i];
		
		if(a<0||b<0)	continue;
		if(dist[a][b])    continue;
		if(dist[t.x][t.y]+1>=fire[a][b]) 	continue;
		
		
		dist[a][b] = dist[t.x][t.y] + 1;
		q[++tt]={a,b};
		
		if(fire[a][b]==-1)	return dist[a][b];
	}
	}
	return -1;
}
int main()
{
	memset(fire,-1,sizeof fire);
	cin>>m;
	while(m--)
	{
		int x1,y1,t;
		cin>>x1>>y1>>t;
	    if(fire[x1][y1]==-1)
	    {
	    	fire[x1][y1]=t;
		}
		for(int i=0;i<4;i++)
		{
			int a = x1 + dx[i];
			int b = y1 + dy[i];
			if(a<0||a>301||b<0||b>301)
			{
				continue;
			 } 
			if(fire[a][b]==-1)
	    {
	    	fire[a][b]=t;
		}
		} 
	}
	int k=bfs();
	cout<<k;
	return 0;
}
2023/10/24 22:29
加载中...