t记录每个格子最早被砸的时间,bfs(x,y,t)表示当前状态为(x,y)格子,时间为t。因为bfs,所以先搜到的t一定小于后搜到的,所以一个格子搜一次就行

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=505,inf=1e9,dx[]={-1,1,0,0,0},dy[]={0,0,-1,1,0};
int n,m,t[N][N];
bool v[N][N];
struct qwe
{
int x,y,t;
qwe(int X=0,int Y=0,int T=0)
{
x=X,y=Y,t=T;
}
};
queue<qwe>q;
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
inline bool ok(int x,int y,int z)
{
return x>=0&&y>=0&&t[x][y]>z&&!v[x][y];
}
int main()
{
n=read();
for(int i=0;i<=500;i++)
for(int j=0;j<=500;j++)
t[i][j]=inf;
for(int i=1;i<=n;i++)
{
int x=read(),y=read(),z=read();
for(int j=0;j<5;j++)
if(x+dx[j]>=0&&y+dy[j]>=0)
t[x+dx[j]][y+dy[j]]=min(t[x+dx[j]][y+dy[j]],z);
}
q.push(qwe(0,0,0));
v[0][0]=1;
while(!q.empty())
{
int x=q.front().x,y=q.front().y,z=q.front().t;
q.pop();
if(t[x][y]==inf)
{
printf("%d\n",z);
return 0;
}
for(int i=0;i<4;i++)
if(ok(x+dx[i],y+dy[i],z+1))
{
v[x+dx[i]][y+dy[i]]=1;
q.push(qwe(x+dx[i],y+dy[i],z+1));
}
}
puts("-1");
return 0;
}

最新文章

  1. mongodb安装&amp;简单使用
  2. Linux内核模块开发基础【转】
  3. go语言 hello 小结
  4. [转载]单元测试之道(使用NUnit)
  5. Linux iptables重启后失效
  6. Oracle中in和exists的选择
  7. 新买一款打印机hp5525N
  8. android:android:background=&quot;#00000000&quot;,透明效果
  9. ZOJ 3940 Modulo Query
  10. HDU3790
  11. PowerShell使用-debug定位问题
  12. ios项目开发汇总
  13. 阿里巴巴图标库iconfont上传svg后,显示不了图片
  14. windows命令行下用netsh实现端口转发(端口映射)
  15. Repeater 控件使用总结
  16. Redis之无序集合类型命令
  17. chrome 调试参数大全
  18. Alpha冲刺(5/10)——追光的人
  19. python 初级/中级/高级/核心
  20. 多线程、多进程、协程、IO多路复用请求百度

热门文章

  1. Android渲染器Shader:LinearGradient(一)
  2. Android TextView内容过长加省略号
  3. Codeforces Round #457 (Div. 2) B
  4. Parent and son
  5. Codeforces 631A Interview【模拟水题】
  6. Ubuntu系统备份工具大全(官方整理推荐)
  7. mysql计算两个日期之间的天数
  8. 在gentoo中打开tomcat的远程调试开关
  9. 华为AR1220
  10. AutoCAD如何设置线宽