Cute_Furina @ 2024-11-23 08:25:39
#include<bits/stdc++.h>
using namespace std;
struct node {
int x, y, t;
}a[500005];
int f[410][410], m, ans, b[410][410];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
bool cmp(node a, node b) {
return a.t < b.t;
}
void dfs(int x, int y, int cnt) {
//cout << x << " " << y <<" " << cnt << " " << f[x][y]<< endl;
if(f[x][y] == 1e9) {
cout << cnt << endl;
exit(0);
}
for(int i = 1;i <= 4;i ++) {
int xx = x + dx[i];
int yy = y + dy[i];
//cout << xx << " " <<< yy << endl;
if(f[xx][yy] > cnt + 1 && xx < 400 && yy < 400 && xx >= 0 && yy >= 0 && b[xx][yy] == 0) {
b[xx][yy] = 1;
dfs(xx, yy, cnt + 1);
}
}
return ;
}
signed main() {
for(int i = 0;i < 400;i ++) {
for(int j = 0;j < 400;j ++) {
f[i][j] = 1e9;
}
}
cin >> m;
for(int i = 1;i <= m;i ++) {
cin >> a[i].x >> a[i].y >> a[i].t;
}
sort(a + 1, a + m + 1, cmp);
for(int i = 1;i <= m;i ++) {
int x = a[i].x, y = a[i].y, t = a[i].t;
f[x][y] = t;
f[x - 1][y] = t;
f[x + 1][y] = t;
f[x][y - 1] = t;
f[x][y + 1] = t;
}
dfs(0, 0, 0);
cout << -1;
return 0;
}by Loyal_Soldier @ 2024-11-23 08:27:38
@Luowj
#include<bits/stdc++.h>
using namespace std;
int n,ans=INT_MAX;
int flag[1000][1000];
int tim[1000][1000];
int f[1000][1000];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
void dfs(int x,int y,int s){
if(x<0||y<0||(flag[x][y]==1&&s>=tim[x][y])||s>=ans||s>=f[x][y])
return;
f[x][y]=s;
if(flag[x][y]==0){
ans=min(ans,s);
return;
}
for(int i=1;i<=4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,s+1);
}
}
int main(){
memset(tim,0xa7f,sizeof(tim));
memset(f,0xa7f,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++){
int t,x,y;
cin>>x>>y>>t;
flag[x][y]=1;
tim[x][y]=min(tim[x][y],t);
for(int j=1;j<=4;j++){
int nx=x+dx[j],ny=y+dy[j];
if(nx>=0&&ny>=0){
flag[nx][ny]=1;
if(t<tim[nx][ny])
tim[nx][ny]=t;
}
}
}
dfs(0,0,0);
if(ans==INT_MAX){
cout<<-1;
return 0;
}
cout<<ans;
return 0;
}