AHOI2005 穿越磁場
本文正體字版由OpenCC轉換
這道題道德解法是離散化+染色+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 < N < 100)。隨後有N行,每行有三個整數X、Y、C(0 < X ,Y ,C < 10000),表示一個磁場左下角座標爲(X,Y),邊長爲C。接下來有一行,共有四個整數SX, SY, TX, TY,表示機器人初始座標爲(SX, SY),礦石座標爲(TX,TY)(其中,1 < SX, SY, TX, TY < 10000)。
輸出:單行輸出一個整數,表示機器人最少需要穿越多少次磁場邊緣。
樣例:
輸入:
<pre>2
1 3 3
2 1 4
0 0 3 4</pre>
輸出:
<pre>2</pre>
</div>
上次修改時間 2017-05-22