bzoj3383[Usaco2004 Open]Cave Cows 4 洞穴里的牛之四

题意:

平面直角坐标系有n个点,从(0,0)出发,从一个点上可以跳到所有与它横纵坐标距离都≤2的点上,求最少步数使得纵坐标为T。

题解:

先用set存下所有的点。在做dp的时候把所有横纵坐标与当前节点距离≤2的节点都在set中查找,如果可以查到则可以转移到那个节点。

代码:

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#define maxn 50010
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int x[maxn],y[maxn],n,t,dis[maxn]; queue<int>q;
struct nd{
int x,y,id;
bool operator < (const nd &a)const{return x!=a.x?x<a.x:y<a.y;}
};
set<nd>st;
int main(){
n=read(); t=read(); inc(i,,n)x[i]=read(),y[i]=read(),st.insert((nd){x[i],y[i],i});
q.push(); dis[]=;
while(!q.empty()){
int z=q.front(); q.pop();
inc(i,-,)inc(j,-,){
set<nd>::iterator a=st.find((nd){x[z]+i,y[z]+j,});
if(a!=st.end()){
dis[a->id]=dis[z]+; q.push(a->id);
if(a->y==t){printf("%d",dis[a->id]); return ;} st.erase(a);
}
}
}
printf("-1"); return ;
}

20160912

最新文章

  1. .NET Framework 4.5.2 静默安装参数
  2. es6 import export 与 node 中的module.exports exports
  3. Guess Number Higher or Lower II--困惑
  4. ARM汇编
  5. Spring Boot 框架@Temporal(TemporalType.DATE)
  6. 转载:jsp中jstl标签的类似 if - else 语句 的语法
  7. WebViewClient shouldOverrideUrlLoading 常见错误用法
  8. Java集合的运算之减法A-B
  9. Firefox插件一键切换兼容IE
  10. Hansight
  11. 总结:ARM逻辑和高级C(朱老师物联网学习)
  12. 【Hybrid App】Hybrid App开发 四大主流移平台分析
  13. POJ2485 Highways(最小生成树)
  14. sql: sql developer tunnel转接
  15. HDU更多的学校比赛9场 HDU 4965Fast Matrix Calculation【矩阵运算+数学技巧】
  16. &lt;bits/stdc++.h&gt;头文件介绍(包含源代码)
  17. api-gateway实践(01)服务网关 - 原型功能
  18. web前端 DOM 详解
  19. 30K iOS程序员的简述:如何快速进阶成为高级开发人员
  20. mybatis 多个接口参数的注解使用方式(@Param)

热门文章

  1. MDK未添加相应芯片的安装包
  2. matlab中imwrite函数详解(imwrite的输出格式)
  3. tomcat中AJP协议和HTTP协议的区别
  4. JavaWeb网上图书商城完整项目--day02-28.查询所有分类功能之left页面使用Q6MenuBar组件显示手风琴式下拉菜单
  5. 3、尚硅谷_SSM高级整合_使用ajax操作实现增加员工的功能
  6. mybatis面试入门
  7. 入门大数据---Flink学习总括
  8. LeetCode65. 有效数字
  9. Python之浅谈继承
  10. 4 个好用的 Linux 监控工具