USACO - Sample Program Test
/*
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;
}
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
登录后可见
用户更多文章推荐
- Bohemian Rhapsody - Queen2021-10-10
- The One You Love - Glenn Grey2020-08-09
- Magic - Coldplay2020-02-24
- You are not there2018-12-11
- Give Me A Reason2018-12-08
- All Of Me2018-12-05
- Spanish Sahara - Foals2018-11-30
- We Are the Champions2018-11-21
- You're Beautiful2018-11-21
- Roar2018-11-21
- Maggie May2018-11-21
- Dangerously2018-11-21
- Let Her Go2018-11-20
- Hey, Soul Sister2018-11-20
- Apologize - Timbaland2018-11-20
- We Are Young - Fun.2018-11-20
- Cheap Thrills2018-11-20
- Stay With Me2018-11-10
- Good Time2018-11-10
- Baby - Justin Bieber2018-11-10
- Party in the U.S.A.2018-11-10