USACO - Sample Program Test

貢獻者:TimDSF 類別:代码 時間:2018-10-02 15:43:38 收藏數:7 評分:0
返回上页 舉報此文章
请选择举报理由:




收藏到我的文章 改錯字
/*
Lasers and Mirrors (C++)
Username: TimDSF
Contest: USACO 2016 December Contest, Gold
Score: 1000/1000
*/
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int x,y,i;
}a[100005];
int n,dis[100005];
vector<int> gx[100005],gy[100005];
bool cmpX(node x1,node x2){
return x1.x<x2.x;
}
bool cmpY(node x1,node x2){
return x1.y<x2.y;
}
bool cmpI(node x1,node x2){
return x1.i<x2.i;
}
int main(){
vector<int>::iterator ii;
queue< pair<int,int> > Q;
freopen("lasers.in","r",stdin);
freopen("lasers.out","w",stdout);
int i,u,v,w,x,y,tmp[100005];
scanf("%d",&n);
scanf("%d%d",&a[1].x,&a[1].y);
scanf("%d%d",&a[n+2].x,&a[n+2].y);
a[1].i=1;
a[n+2].i=n+2;
n+=2;
for (i=2;i<n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].i=i;
}
sort(a+1,a+n+1,cmpX);
tmp[1]=1;
for (i=2;i<=n;i++){
if (a[i].x==a[i-1].x){
tmp[i]=tmp[i-1];
}else{
tmp[i]=tmp[i-1]+1;
}
}
for (i=1;i<=n;i++){
a[i].x=tmp[i];
}
for (i=1;i<=n;i++){
gx[a[i].x].push_back(a[i].i);
}
sort(a+1,a+n+1,cmpY);
tmp[1]=1;
for (i=2;i<=n;i++){
if (a[i].y==a[i-1].y){
tmp[i]=tmp[i-1];
}else{
tmp[i]=tmp[i-1]+1;
}
}
for (i=1;i<=n;i++){
a[i].y=tmp[i];
}
for (i=1;i<=n;i++){
gy[a[i].y].push_back(a[i].i);
}
sort(a+1,a+n+1,cmpI);
Q.push(make_pair(1,0));
while(!Q.empty()){
u=Q.front().first;
w=Q.front().second;
if (u==n){
printf("%d\n",w-1);
return 0;
}
Q.pop();
x=a[u].x;
y=a[u].y;
for (ii=gx[x].begin();ii!=gx[x].end();ii++){
v=*ii;
Q.push(make_pair(v,w+1));
gx[x].erase(ii);
ii--;
}
for (ii=gy[y].begin();ii!=gy[y].end();ii++){
v=*ii;
Q.push(make_pair(v,w+1));
gy[y].erase(ii);
ii--;
}
}
printf("-1\n");
return 0;
}
声明:以上文章均为用户自行添加,仅供打字交流使用,不代表本站观点,本站不承担任何法律责任,特此声明!如果有侵犯到您的权利,请及时联系我们删除。
文章熱度:
文章難度:
文章質量:
說明:系統根據文章的熱度、難度、質量自動認證,已認證的文章將參與打字排名!

本文打字排名TOP20

用户更多文章推荐