LabmemNo_012LzTopic @ 2024-07-27 16:17:33
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct ll
{
int x;
int y;
int t;
}ys[50005];
struct lll
{
int x[315];
int y[315];
int sum = 0;
}qz[315];
int map[315][315] = { 0 }, n, fx[4] = { -1,1,0,0 }, fy[4] = { 0,0,-1,1 },
x, y, xl, yl, in, ans = 999;
void BFS(int k)
{
if (qz[k].sum == 0)return;
if (ys[in].t == -1)return;
for (int i = 1; i <= qz[k].sum; i++)
{
x = qz[k].x[i];
y = qz[k].y[i];
if (map[x][y] == -1)continue;
for (int j = 0; j < 4; j++)
{
xl = x + fx[j];
yl = y + fy[j];
if (xl < 0)continue;
if (yl < 0)continue;
if (map[xl][yl] == 0)
{
map[xl][yl] = k + 1;
qz[k + 1].sum++;
qz[k + 1].x[qz[k+1].sum] = xl;
qz[k + 1].y[qz[k + 1].sum] = yl;
}
}
}
if (ys[in].t == k + 1)
{
while (ys[in].t == k + 1)
{
x = ys[in].x;
y = ys[in].y;
map[x][y] = -1;
for (int j = 0; j < 4; j++)
{
xl = x + fx[j];
yl = y + fy[j];
if (xl < 0)continue;
if (yl < 0)continue;
map[xl][yl] = -1;
}
in++;
}
}
BFS(k + 1);
}
int main()
{
int max = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> ys[i].x >> ys[i].y >> ys[i].t;
if (ys[i].t > max)max = ys[i].t;
}
ys[n + 1].t = -1;
qz[0].x[1] = 0;
qz[0].y[1] = 0;
qz[0].sum = 1;
map[0][0] = 999;
in = 1;
BFS(0);
for (int i = 0; i <= max; i++)
{
for (int j = 0; j <= max; j++)
{
if (map[i][j] <= 0)continue;
if (map[i][j] < ans)ans = map[i][j];
}
}
if (map[0][0] == 999)ans = 0;
if (ans == 999)ans = -1;
cout << ans << endl;
return 0;
}
by LabmemNo_012LzTopic @ 2024-08-02 11:00:41
ai