水水的BFS，说它水，是因为我用了STL，哈哈。
STL是个好东东！
CO
/*
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 on
straight north, east, south, or west. She can’t push herself through
the rock, of course, and thus generally has on
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 on
encountering a rock head on. On
(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 on
north has a rock for stopping. For situation (b), she can slide
on
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 on
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;
}