yuxiaoyu20090104 @ 2022-09-21 23:18:01
#include<bits/stdc++.h>
using namespace std;
int a[505][505];//记录每个点流星砸下的时间
int t[505][505];//记录奶牛走到每个点所需的时间
struct node { int x, y; };
queue<node> qu;
int dx[5] = { -1,0,0,1 };
int dy[5] = { 0,-1,1,0 };
int M;
int now;
int main() {
cin >> M;
memset(a, -1, sizeof(a));
for (int i = 1; i <= M; i++)
{
int x, y, time;
cin >> x >> y >> time;
if (a[x][y] == -1 || time <= a[x][y])
{
a[x][y] = time;
for (int j = 0; j < 4; j++)
{
int nx = x + dx[j], ny = y + dy[j];
if (nx >= 0 && ny >= 0 && (time < a[nx][ny] || a[nx][ny] == -1))a[nx][ny] = time;
}
}
}
qu.push({ 0,0 });
t[0][0] = 0;
if (a[0][0] == -1)
{
cout << 0;
return 0;
}
while (!qu.empty())
{
int x0 = qu.front().x, y0 = qu.front().y;
qu.pop();
for (int i = 0; i < 4; i++)
{
int nx = x0 + dx[i], ny = y0 + dy[i];
if (nx >= 0 && ny >= 0 && (a[nx][ny] > t[x0][y0] + 1 || a[nx][ny] == -1))
{
t[nx][ny] = t[x0][y0] + 1;
if (a[nx][ny] == -1)
{
cout << t[nx][ny];
return 0;
}
qu.push({ nx,ny });
}
}
}
cout << -1;
return 0;
}
by zwqyyds @ 2022-09-25 08:10:47
这是需要判断一下,只有当这颗流星到达的时间小于前面流星到达的时间,才能把时间赋值给数组,而不能直接覆盖