『ice 离散化广搜』

<更新提示>

<第一次更新>

<正文>

ice(USACO)

Description

Bessie 在一个冰封的湖面上游泳，湖面可以表示为二维的平面，坐标范围是-1,000,000,000..1,000,000,000。

湖面上的N(1 <= N <= 20,000)个位置有石块(编号分别为1到N)，其它位置是冰面。

由于Bessie滑冰技术不够好，她通过推动自己旁边的石块，依靠反作用力向某一个方向前进，在碰到一个新的石块之前，Bessie是不会停下来的。(当然，最后会停留在某块石块的前一个格子里)由于Bessie无法计算复杂的角度，她只能够向东南西北四个方向前进。

很显然，Bessie不能够穿越石块，因此，Bessie仅仅可以向三个方向滑。

滑冰不是没有风险，Bessie滑向某个方向后必须能碰到某个石块，因此她必须很小心。

考虑下面的一个情况，Bessie希望到达在她东面的目标位置(x=5,y=1)，(. = 冰块,* = 石头, B = Bessie, G = 目的位置)如果她直接向东滑，那么她会滑过目标位置，因为她通过撞上某块石头来停下来，一个能够到达目标位置的方案是这样的：



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

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

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

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

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

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

在(a)中，Bessie 只能朝向北，东，或者南三个方向，但是只有在北面能撞上石头从而停下来，在(b)中，类似地，她只能向东走。

对于输入，石头 i位于坐标为X_i,Y_i的位置，(-1,000,000,000<= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000)，没有任何两块石头位于同一个位置，Bessie从Bx,By的位置出发(出发点一定与某个石头相邻)，Bessie的目标位置是Gx,Gy(-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=1,000,000,000).

Bessie 并不介意长时间滑冰，但是，不停地推石头依靠反作用力前进很累。FJ 非常关心Bessie的健康，因此他希望知道Bessie最少要推多少次石头才能到达终点。

Input Format

第一行: 五个用空格隔开的整数: N, Bx, By, Gx, and Gy
第二行到第N+1行: 第i+1行用两个空格隔开的整数来描述第i个石头

Output Format

第一行: 一个整数表示Bessie至少要推多少次石头才能够到达终点

Sample Input

Sample Output

解析

简单地来看的话，这道题显然是一个广搜，每一个状态之间的转移的花费都是\(1\)。

但是问题就是这个"地图"太稀疏了，石头个数只有\(20000\)，而坐标却全是\(int\)范围内的，需要考虑离散化一下。

二维离散化？这样太复杂了些，最好的办法是利用\(STL\)。我们利用\(map\)和\(set\)建立形如map< int,set<int> >这样的一对多的索引数组。对于每一行，我们存下行内所有石头的纵坐标，对于每一列，我们也存下列内所有石头的横坐标。然后对于每一个位置我们就能广搜了。利用\(set\)自带的二分查找函数方便地找到第一个碰撞到的石头，然后就能得到下一个状态了。

当然，记录当前状态的最小花费的数组也是用\(map\)的。

\(Code:\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define mset(name,val) memset(name,val,sizeof name)

#define filein(str) freopen(str".in","r",stdin)

#define fileout(str) freopen(str".out","w",stdout)

#define node pair<int,int>

#define x first

#define y second

const int N=20020;

int n;

node Begin,End;

map < node,int > dis;

map < int,set < int > > row,col;

inline void input(void)

{

	scanf("%d%d%d%d%d",&n,&Begin.x,&Begin.y,&End.x,&End.y);

	for(int i=1;i<=n;i++)

	{

		node t;

		scanf("%d%d",&t.x,&t.y);

		row[t.x].insert(t.y);col[t.y].insert(t.x);

	}

}

inline node findup(node temp)

{

	set < int > s=col[temp.y];

	set < int > :: iterator it=s.lower_bound(temp.x);

	if(it==s.begin()||temp.x-(*(--it))<=1)

		return temp;

	return (node){(*it)+1,temp.y};

}

inline node finddown(node temp)

{

	set < int > s=col[temp.y];

	set < int > :: iterator it=s.upper_bound(temp.x);

	if(it==s.end()||(*it)-temp.x<=1)

		return temp;

	return (node){(*it)-1,temp.y};

}

inline node findright(node temp)

{

	set < int > s=row[temp.x];

	set < int > :: iterator it=s.upper_bound(temp.y);

	if(it==s.end()||(*it)-temp.y<=1)

		return temp;

	return (node){temp.x,(*it)-1};

}

inline node findleft(node temp)

{

	set < int > s=row[temp.x];

	set < int > :: iterator it=s.lower_bound(temp.y);

	if(it==s.begin()||temp.y-(*(--it))<=1)

		return temp;

	return (node){temp.x,(*it)+1};

}

inline void bfs(void)

{

	queue < node > q;

	q.push(Begin);

	dis[Begin]=0;

	while(!q.empty())

	{

		node temp=q.front();q.pop();

		if(temp==End)break;

		node next=findup(temp);

		if(next!=temp&&!dis[next])

		{

			dis[next]=dis[temp]+1;

			q.push(next);

		}

		next=finddown(temp);

		if(next!=temp&&!dis[next])

		{

			dis[next]=dis[temp]+1;

			q.push(next);

		}

		next=findleft(temp);

		if(next!=temp&&!dis[next])

		{

			dis[next]=dis[temp]+1;

			q.push(next);

		}

		next=findright(temp);

		if(next!=temp&&!dis[next])

		{

			dis[next]=dis[temp]+1;

			q.push(next);

		}

	}

}

int main(void)

{

	filein("ice.");

	fileout("ice.");

	input();

	bfs();

	printf("%d\n",dis[End]);

	return 0;

}

<后记>

巴特西