wyp20130701 @ 2024-11-14 17:49:07
#include <bits/stdc++.h>
using namespace std;
int ans[305][305], death[305][305];
void MIN(int x, int y, int t){
if (x >= 0 && y >= 0)
death[x][y] = min(death[x][y], t);
return;
}
struct coord{
int x, y;
};
queue<coord> q;
int nxt[4][2] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
memset(ans, -1, sizeof(ans));
memset(death, 0x7f, sizeof(death));
for (int i = 1; i <= n; ++i){
int x, y, t;
cin >> x >> y >> t;
MIN(x, y, t);
for (int i = 0; i < 4; ++i) MIN(x + nxt[i][0], y + nxt[i][1], t);
}
q.push((coord){0, 0});
ans[0][0] = 0;
while (!q.empty()){
coord now = q.front();
q.pop();
int x = now.x, y = now.y;
for (int i = 0; i < 4; ++i){
int ux = x + nxt[i][0], uy = y + nxt[i][1];
if (ux < 0 || uy < 0 || ans[ux][uy] != -1 || ans[x][y] + 1 >= death[ux][uy]) continue;
ans[ux][uy] = ans[x][y] + 1;
q.push((coord){ux, uy});
}
}
int Ans = INT_MAX;
for (int i = 0; i <= 305; ++i)
for (int j = 0; j <= 305; ++j)
if (death[i][j] >= 100000 && ans[i][j] != -1)
Ans = min(Ans, ans[i][j]);
if (Ans == INT_MAX)
puts("-1");
else
cout << Ans << "\n";
return 0;
}
就21分
by heyichen123 @ 2024-11-14 18:11:06
@wyp20130701 ??????
by wyp20130701 @ 2024-11-14 18:12:37
咋了?