注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

USACO[Elite 2010 February Competition/gold]ice  

2010-04-22 19:29:37|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

水水的BFS,说它水,是因为我用了STL,哈哈。

STL是个好东东!

CODE:

/*

PROG: ice

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Cows on Ice [Jelle van den Hooff, 2010]

CONTENT:

Bessie is ice skating on a large frozen lake modelled as a 2-dimensional

grid with coordinates in the range -1,000,000,000..1,000,000,000.

N (1 <= N <= 20,000) of the lake's grid cells contain rocks

(conveniently numbered 1..N). The other cells contain slippery ice.

Since Bessie is not a very good skater, she traverses the lake's

cells by pushing herself away from her current position near a rock

and sliding continuously in the same direction until she hits another

rock (stopping in the square before she hits the rock, of course).

Never good with complicated angles, Bessie can push herself only

straight north, east, south, or west. She can't push herself through

the rock, of course, and thus generally has only three possible

directions to move.

Sliding is not without risks. Bessie must hit a rock or might end

up sliding for a very long time. She must aim her pushes carefully.

Consider the situation depicted below; Bessie wants to get to

location (x=5,y=1), which is east of her current location (. = ice,

* = rock, B = Bessie, G = goal). If she slides directly to the east,

she will slide past the location since she can stop only by

encountering a rock head on. One way to get to (5,1) is the following:

   (a)              (b)             (c)              (d)

4 .....*.         .....*.         .....*.          .....*.

3 ..*....  slide  ..*....  slide  ..*....   slide  ..*....

2 ......*  north  ..B...*  east   .....B*   south  ......*

1 .*B..G. ------> .*...G. ------> .*...G.  ------> .*...B.

0 *....*.         *....*.         *....*.          *....*.

  0123456

Bessie could slide north, east, or south in situation (a), but only

north has a rock for stopping. For situation (b), she can slide

only east for the same reason.

For the input, rock i is located at cell X_i,Y_i (-1,000,000,000

<= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000),

and no two rocks occupy the same position. Bessie starts at Bx,By

(which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000;

-1,000,000,000 <= By <= 1,000,000,000). Bessie's goal is Gx,Gy

(-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=

1,000,000,000). Bessie can always reach the goal one way or another.

Bessie doesn't mind sliding. However, pushing herself away from a

rock is very tiring. To prepare her, FJ would like to know the

minimum number of pushes Bessie needs to do.

PROBLEM NAME: ice

INPUT FORMAT:

* Line 1: Five space separated integers: N, Bx, By, Gx, and Gy

* Lines 2..N+1: Line i+1 describes a rock location with space

        separated integers: X_i and Y_i

SAMPLE INPUT (file ice.in):

6 2 1 5 1

5 4

2 3

1 1

6 2

5 0

0 0

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of pushes for

        Bessie to get to her goal

SAMPLE OUTPUT (file ice.out):

3

*/

#include <stdio.h>

#include <set>

using std::set;

#include <map>

using std::map;

#include <queue>

using std::queue;

using std::pair;

using std::make_pair;

 

const int MAXN=20000;

int N,Bx,By,Gx,Gy;

int X[MAXN],Y[MAXN];

 

int main()

{

    freopen("ice.in","r",stdin);

    freopen("ice.out","w",stdout);

    scanf("%d %d %d %d %d\n",&N,&Bx,&By,&Gx,&Gy);

    for (int i=0;i<N;i++)

        scanf("%d %d\n",&X[i],&Y[i]);

   

    map<int,set<int> > x;

    map<int,set<int> > y;

    for (int i=0;i<N;i++)

    {

        x[X[i]].insert(Y[i]);

        y[Y[i]].insert(X[i]);

    }

    set<pair<int,int> > inq;

    queue<pair<pair<int,int>,int> > q;

    inq.insert(make_pair(Bx,By));

    q.push(make_pair(make_pair(Bx,By),0));

    for (;;)

    {

        int get_x=q.front().first.first,

            get_y=q.front().first.second;

        //printf("get:%d %d value%d\n",get_x,get_y,q.front().second);

        if (get_x==Gx&&get_y==Gy) break;       

        map<int,set<int> >::iterator xit=x.find(get_x),yit=y.find(get_y);

        set<int>::iterator it;

        if (xit!=x.end())

        {

           it=xit->second.upper_bound(get_y);

           if (it!=xit->second.end())

              if (inq.find(make_pair(get_x,*it-1))==inq.end())

              {

                 q.push(make_pair(make_pair(get_x,*it-1),q.front().second+1));

                 inq.insert(make_pair(get_x,*it-1));

              }

           if (it!=xit->second.begin())

           {

              it--;

              if (inq.find(make_pair(get_x,*it+1))==inq.end())

              {

                 q.push(make_pair(make_pair(get_x,*it+1),q.front().second+1));

                 inq.insert(make_pair(get_x,*it+1));

              }

           }

        }

        if (yit!=y.end())

        {

           it=yit->second.upper_bound(get_x);

           if (it!=yit->second.end())

              if (inq.find(make_pair(*it-1,get_y))==inq.end())

              {

                 q.push(make_pair(make_pair(*it-1,get_y),q.front().second+1));

                 inq.insert(make_pair(*it-1,get_y));

              }

           if (it!=yit->second.begin())

           {

              it--;

              if (inq.find(make_pair(*it+1,get_y))==inq.end())

              {

                 q.push(make_pair(make_pair(*it+1,get_y),q.front().second+1));

                 inq.insert(make_pair(*it+1,get_y));

              }

           }

        }

        q.pop();

    }

   

    printf("%d\n",q.front().second);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}

 

  评论这张
 
阅读(649)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018