This post is written in Chinese. Please consider using Google Translate

这道题道德解法是离散化+染色+BFS最短路径。首先，由于坐标范围很大，离散化处理是很有必要的，这样可以把坐标范围从10000压缩到210以内。在离散化以后的格子中进行一次Floodfill，对每个封闭区域进行染色处理。接下来，把每个染色区域看成图中的一个顶点，相邻的染色区域建立一条权值为1的无向边。最后，求S到T所在染色区域对应顶点之间的最短路径，由于边权全部为1，只需一边BFS即可。

这道题是大名鼎鼎的《骗分导论》上的一道例题，除了骗分以外，这种解法也是非常好的。

/* 
 * Problem: AHOI2005 cross
 * Author: Guo Jiabao
 * Time: 2009.4.17 10:32
 * State: Solved
 * Memo: 离散化 + 染色 + BFS
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXL=405,INF=0x7FFFFFF,MAXC=MAXN*MAXN;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
using namespace std;
struct Queue
{
    int Q[MAXC],head,tail,size;
    Queue() {head=size=0;tail=-1;}
    void ins(int p)
    {
        if (++tail>=MAXC) tail=0;
        Q[tail]=p;
        size++;
    }
    int pop()
    {
        int r=Q[head];
        if (++head>=MAXC) head=0;
        size--;
        return r;
    }
}Q;
struct edge
{
    edge *next;
    int t;
}*V[MAXC];
struct point
{
    int x,y;
}S,T,Rect[MAXN][2],*P[MAXN*2+3],MaxP;
int N,CP,Color,Start,Target,Ans;
int TK[MAXN*2+3];
int Bel[MAXL][MAXL];
int Dist[MAXC];
void init()
{
    int i,x,y,c;
    freopen("cross.in","r",stdin);
    freopen("cross.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        Rect[i][0].x=x;Rect[i][0].y=y;
        Rect[i][1].x=x+c;Rect[i][1].y=y+c;
        P[++CP]=&Rect[i][0]; P[++CP]=&Rect[i][1];
    }
    scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
    P[++CP]=&S; P[++CP]=&T;
}
inline int cmpx(const void *a,const void *b)
{
    point *A=*(point **)a, *B=*(point **)b;
    return A->x - B->x;
}
inline int cmpy(const void *a,const void *b)
{
    point *A=*(point **)a, *B=*(point **)b;
    return A->y - B->y;
}
void dispose()
{
    int i;point PT={-100000,-100000};
    MaxP.x=MaxP.y=0;
    P[0]=&PT;TK[0]=0;
    qsort(P+1,CP,sizeof(P[0]),cmpx);
    for (i=1;i<=CP;i++)
    {
        TK[i]=TK[i-1];
        if (P[i]->x!=P[i-1]->x)
            TK[i]++;
        if (TK[i] > MaxP.x)
            MaxP.x=TK[i];
    }
    for (i=1;i<=CP;i++)
        P[i]->x=TK[i];
    qsort(P+1,CP,sizeof(P[0]),cmpy);
    for (i=1;i<=CP;i++)
    {
        TK[i]=TK[i-1];
        if (P[i]->y!=P[i-1]->y)
            TK[i]++;
        if (TK[i] > MaxP.y)
            MaxP.y=TK[i];
    }
    for (i=1;i<=CP;i++)
        P[i]->y=TK[i];
}
inline bool inrange(int x,int y)
{
    return x>=0 && y>=0 && x<=MaxP.x+1 && y<=MaxP.y+1;
}
inline bool inrect(int x,int y,int k)
{
    return x>=Rect[k][0].x && x<Rect[k][1].x && y>=Rect[k][0].y && y<Rect[k][1].y;
}
bool cross(int x1,int y1,int x2,int y2)
{
    int i;
    for (i=1;i<=N;i++)
    {
        if (inrect(x1,y1,i) ^ inrect(x2,y2,i))
            return true;
    }
    return false;
}
void dfscolor(int x,int y)
{
    int k,tx,ty;
    Bel[x][y]=Color;
    for (k=0;k<4;k++)
    {
        tx=x+dx[k]; ty=y+dy[k];
        if (inrange(tx,ty) && !Bel[tx][ty] && !cross(x,y,tx,ty))
        {
            dfscolor(tx,ty);
        }
    }
}
void floodfill()
{
    int x,y;
    for (x=1;x<MaxP.x;x++)
    {
        for (y=1;y<MaxP.y;y++)
        {
            if (!Bel[x][y])
            {
                Color++;
                dfscolor(x,y);
            }
        }
    }
}
inline void addedge(int a,int b)
{
    edge e={V[a],b};
    V[a]=new edge(e);
}
void MakeGraph()
{
    int x,y,tx,ty,k,a,b;
    for (x=1;x<=MaxP.x;x++)
    {
        for (y=1;y<=MaxP.y;y++)
        {
            a=Bel[x][y];
            if (x==S.x && y==S.y)
                Start=a;
            if (x==T.x && y==T.y)
                Target=a;
            for (k=0;k<4;k++)
            {
                tx=x+dx[k]; ty=y+dy[k];
                if (inrange(tx,ty))
                {
                    b=Bel[tx][ty];
                    addedge(a,b);
                }
            }
        }
    }
}
void BFS()
{
    int i,j;
    memset(Dist,-1,sizeof(Dist));
    Q.ins(Start);
    Dist[Start]=0;
    while (Q.size)
    {
        i=Q.pop();
        for (edge *e=V[i];e;e=e->next)
        {
            j=e->t;
            if (Dist[j]==-1)
            {
                Dist[j]=Dist[i]+1;
                if (j==Target)
                    return;
                Q.ins(j);
            }
        }
    }
}
void solve()
{
    dispose();
    floodfill();
    MakeGraph();
    BFS();
    Ans=Dist[Target];
}
int main()
{
    init();
    solve();
    printf("%d\n",Ans);
    return 0;
}

<div class="MainText">

<a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=316" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=316</a>

<strong>穿越磁场</strong>

探险机器人在Samuel星球上寻找一块奇特的矿石，然而此时它陷入了一片神秘的磁场区域，动弹不得。

探险空间站立刻扫描了这片区域，绘制出该区域的磁场分布平面图。这片区域中分布了N个磁场，每个磁场呈正方形，且边与坐标轴平行。

例如下图中，存在3个磁场，白点表示机器人的位置，黑点表示矿石的位置：

<span class="image"><a href="http://192.168.1.253/mw/images/e/ea/Cross_1.gif"><img src="http://192.168.1.253/mw/images/e/ea/Cross_1.gif" alt="Image:Cross 1.gif" width="355" height="192" /></a></span>

科学家们分析平面图，进一步发现：这些磁场为大小不一的正方形，可能相交，甚至覆盖，但是它们的边缘不会重合，顶点也不会重合。

例如下面的两种情形是不会出现的：

<a href="http://192.168.1.253/mw/images/c/ca/Cross_2.gif"><img src="http://192.168.1.253/mw/images/c/ca/Cross_2.gif" alt="Image:Cross 2.gif" width="375" height="122" /></a>

科学家们给探险机器人启动了磁力罩，这样它就可以在磁场中自由穿越了。

初始时，探险机器人和所有矿石都不在任何磁场的边缘。由于技术限制，在穿越过程中机器人只能够水平或垂直移动，且不能够沿着磁场的边缘行动。

由于磁力罩的能量有限，科学家们希望探险机器人穿越尽量少的磁场边缘采集到这块矿石。例如上图中，探险机器人最少需要穿越两次磁场边缘。

现在小联请你编写程序，帮助科学家们设计探险机器人的路线，统计探险机器人最少需要穿越多少次磁场边缘。
输入：第一行有一个整数N，表示有N个磁场（1 &lt; N &lt; 100）。随后有N行，每行有三个整数X、Y、C（0 &lt; X ,Y ,C &lt; 10000），表示一个磁场左下角坐标为（X,Y），边长为C。接下来有一行，共有四个整数SX, SY, TX, TY，表示机器人初始坐标为（SX, SY），矿石坐标为（TX，TY）（其中，1 &lt; SX, SY, TX, TY &lt; 10000）。
输出：单行输出一个整数，表示机器人最少需要穿越多少次磁场边缘。
样例：

输入：
<pre>2
1 3 3
2 1 4
0 0 3 4</pre>
输出：
<pre>2</pre>
</div>