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