丨Sky灬丨无惧 @ 2021-02-21 20:21:56
RT 代码:
#include<bits/stdc++.h>
using namespace std;
int m,bj=1,ans=-1,z[600][600],vis[600][600],r,l=1;
int dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1};
struct sb {
int x,y,z;
};
sb a[2000000],b[2000000];
int cmp(sb c,sb d) {
return c.z<d.z;
}
void push(int x,int y,int z) {
a[++r].x=x;
a[r].y=y;
a[r].z=z;
vis[x][y]=1;
}
void bfs() {
push(0,0,0);
while(l<=r) {
int x2=a[l].x;
int y2=a[l].y;
int z2=a[l].z;
while(z2>=b[bj].z-1) {
vis[b[bj].x][b[bj].y]=1;
vis[b[bj].x+1][b[bj].y]=1;
if(b[bj].x-1>=0)vis[b[bj].x-1][b[bj].y]=1;
vis[b[bj].x][b[bj].y+1]=1;
if(b[bj].y-1>=0)vis[b[bj].x][b[bj].y-1]=1;
bj++;
}
l++;
if(z[x2][y2]==0) {
ans=z2;
return;
}
for(int i=0; i<4; i++) {
int xx=x2+dx[i];
int yy=y2+dy[i];
if(xx<0||yy<0||xx>310||yy>310||vis[xx][yy])continue;
push(xx,yy,z2+1);
}
}
}
int main() {
cin>>m;
for(int i=1; i<=m; i++) {
cin>>b[i].x>>b[i].y>>b[i].z;
z[b[i].x][b[i].y]=1;
z[b[i].x+1][b[i].y]=1;
z[b[i].x][b[i].y+1]=1;
if(b[i].x-1>=0)z[b[i].x-1][b[i].y]=1;
if(b[i].y-1>=0) z[b[i].x][b[i].y-1]=1;
}
sort(b+1,b+1+m,cmp);
bfs();
cout<<ans;
return 0;
}
by 丨Sky灬丨无惧 @ 2021-02-21 20:36:09
@丨Sky灬丨无惧 已解决谢谢
by zc_li @ 2021-02-22 00:30:11
@丨Sky灬丨无惧 你竟然回谷了orz
by zc_li @ 2021-02-22 00:30:47
好久没有一起做题了呢/kk