RingTouSou @ 2023-10-24 22:29:53
这是无穷大的代码
#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;
}