POI 1999 倉庫管理員 Store−keeper
這道題描述的是我們玩過的經典的小遊戲，推箱子。由於要求步數最少，基本的想法是BFS，記錄人的位置和箱子的位置兩個狀態。但是狀態數過多，有100100100100，進一步思考可以發現記錄人的絕對位置是沒有必要的，因爲只有人在箱子旁邊的單元格內，才能推箱子，所以只需記錄箱子的位置和人在箱子的方向，只有100100*4個狀態。
BFS過程中，狀態擴展分類兩種情況，一種是向前推箱子，步數要加1，另一種是改變人的方向。推箱子只需判斷前面的位置是否是空地，如果是障礙則不能繼續擴展。改變人的方向就有些複雜了，假設箱子的位置是(x0,y0)，人原來的位置是(x1,y1)，新的位置是(x2,y2)，則要判斷(x1,y1)到(x2,y2)是否存在不經過(x0,y0)的路徑。簡單的想法是floodfill，時間複雜度爲O(NM)。注意狀態判重，還有就是初始位置的確定。由於人初始不一定在箱子邊，需要floodfill一下，求出人能到達的箱子旁邊的位置，如果根本不能到達，顯然無解。
按這種想法寫出的程序是要超時的，加上些例如我們在玩推箱子的時候不能把箱子推到牆角之類無關緊要的優化，還是無法通過。思考算法的主要瓶頸就在於判斷改變方向時每次都要floodfill一遍，如果能把這裏優化一下，或許就能通過。
進一步思考，發現兩地如果連通，必須至少存在一條路徑，如果總是連通，必須至少存在兩條路徑。也就是說，無論箱子作爲障礙擋在哪條路徑上，總還有另一條路徑使這兩點連通。這恰好是圖論中雙連通分支(點雙連通)的定義，即沒有割點的連通分支。所以可以這樣判斷，對於一個連通圖，如果箱子不在割點上，箱子旁邊的兩點(人的位置)一定連通，如果箱子在割點上，則人的兩點位置是否連通，取決於兩點是否同屬一個雙連通分支。於是我們可以預處理出圖中的所有割點和雙連通分支，然後每次判斷兩點連通只需O(1)的時間。這樣就可以解決這道題了。
/*
* Problem: POI1999 mag
* Author: Guo Jiabao
* Time: 2009.4.8 9:08
* State: Solved
* Memo: BFS 雙連通分支判斷
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=101,MAXN=10001,MAXM=MAXN*8;
const int LEFT=0,RIGHT=1,UP=2,DOWN=3;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
using namespace std;
struct state
{
int x,y,p,step;
};
template<typename T> class linklist
{
public:
T v;
linklist *next;
linklist(T tv):v(tv){next=0;}
};
template<typename T> class Queue
{
public:
linklist<T> *first,*last;
int size;
void clear()
{
size=0;
first=last=0;
}
void ins(T v)
{
size++;
if (first)
last=last->next=new linklist<T>(v);
else
first=last=new linklist<T>(v);
}
T pop()
{
T r=first->v;
linklist<T> *t=first->next;
size--;
delete first;
first=t;
return r;
}
};
struct edge
{
edge *next;
int t;
}ES[MAXM];
edge *V[MAXN];
bool field[MAXL][MAXL],vis[MAXL][MAXL];
bool hash[MAXL][MAXL][4];
int mvb[MAXL][MAXL][4][4],Map[MAXL][MAXL];
int LOW[MAXN],DFN[MAXN],PAR[MAXN],Sta1[MAXM],Sta2[MAXM],Stop,D,Bcnt;
bool isgd[MAXN],bichash[MAXN];
int N,M,Ans,EC=-1,U;
state S,P,T;
Queue<state> Q;
Queue<int> Bel[MAXN];
inline bool inrange(int x,int y)
{
return x>=1 && x<=N && y>=1 && y<=M;
}
inline void addedge(int a,int b)
{
ES[++EC].next=V[a];
V[a]=ES+EC;V[a]->t=b;
ES[++EC].next=V[b];
V[b]=ES+EC;V[b]->t=a;
}
void init()
{
int i,j,k,l;
char c;
freopen("mag.in","r",stdin);
freopen("mag.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
{
do c=getchar(); while (c==10 || c==13);
ungetc(c,stdin);
for (j=1;j<=M;j++)
{
c=getchar();
if (c=='S')
field[i][j]=false;
else
{
field[i][j]=true;
Map[i][j]=++U;
k=i-1,l=j;
if (inrange(k,l) && field[k][l])
addedge(Map[i][j],Map[k][l]);
k=i,l=j-1;
if (inrange(k,l) && field[k][l])
addedge(Map[i][j],Map[k][l]);
}
if (c=='M')
{
S.x=i;S.y=j;
S.step=0;S.p=0;
}
if (c=='P')
P.x=i,P.y=j;
if (c=='K')
T.x=i,T.y=j;
for (k=0;k<4;k++)
for (l=0;l<4;l++)
mvb[i][j][k][l]=2;
}
}
}
inline int getopd(int k)
{
if (k==LEFT) return RIGHT;
if (k==RIGHT) return LEFT;
if (k==UP) return DOWN;
return UP;
}
bool start(state i)
{
int k,r;
for (k=0;k<4;k++)
{
state j;
j.x=i.x+dx[k]; j.y=i.y+dy[k];
if (inrange(j.x,j.y) && field[j.x][j.y] && !vis[j.x][j.y])
{
vis[j.x][j.y]=true;
if (j.x==P.x && j.y==P.y)
{
P.p=getopd(k);
return true;
}
else
r=start(j);
if (r) return true;
}
}
return false;
}
inline bool insamebic(int u,int v)
{
linklist<int> *k;
bool rs=false;
for (k=Bel[u].first;k;k=k->next)
bichash[k->v]=true;
for (k=Bel[v].first;k;k=k->next)
if (bichash[k->v])
{
rs=true;
break;
}
for (k=Bel[u].first;k;k=k->next)
bichash[k->v]=false;
return rs;
}
bool movable(int bx,int by,int ps,int pd)
{
if (mvb[bx][by][ps][pd]==2)
{
if (isgd[Map[bx][by]])
{
int k=ps,x,y;
state p,q;
p.x=bx+dx[k]; p.y=by+dy[k];
k=pd;
q.x=bx+dx[k]; q.y=by+dy[k];
x=Map[p.x][p.y]; y=Map[q.x][q.y];
mvb[bx][by][ps][pd]=insamebic(x,y);
}
else
mvb[bx][by][ps][pd]=true;
}
return mvb[bx][by][ps][pd];
}
bool BFS()
{
state i,j;
int k;
Q.clear();
Q.ins(P);
hash[P.x][P.y][P.p]=true;
while (Q.size)
{
i=j=Q.pop();
//move direction
for (k=0;k<4;k++)
{
j.x=i.x+dx[k]; j.y=i.y+dy[k];
if (inrange(j.x,j.y) && field[j.x][j.y])
{
j.x=i.x;j.y=i.y;j.p=k;
if (!hash[j.x][j.y][j.p] && movable(i.x,i.y,i.p,j.p))
{
hash[j.x][j.y][j.p]=true;
Q.ins(j);
}
}
}
j.step=i.step+1;
//push box
k=getopd(i.p);
j.x=i.x+dx[k]; j.y=i.y+dy[k]; j.p=i.p;
if (inrange(j.x,j.y) && field[j.x][j.y] && !hash[j.x][j.y][j.p])
{
if (j.x==T.x && j.y==T.y)
{
Ans=j.step;
return true;
}
hash[j.x][j.y][j.p]=true;
Q.ins(j);
}
}
return false;
}
void addbic(int B,int u)
{
linklist<int> *k;
for (k=Bel[u].first;k;k=k->next)
if (k->v==B)
return;
Bel[u].ins(B);
}
void bic(int u,int p)
{
DFN[u]=LOW[u]=++D;
for (edge *k=V[u];k;k=k->next)
{
int v=k->t;
if (v==p) continue;
if (DFN[v]<DFN[u]) //避免橫叉邊
{
Stop++;Sta1[Stop]=u;Sta2[Stop]=v;
if (!DFN[v])
{
bic(v,u);
if (LOW[v]<LOW[u])
LOW[u]=LOW[v];
if (DFN[u]<=LOW[v])
{
isgd[u]=true;
int x,y;
Bcnt++;
do
{
x=Sta1[Stop];y=Sta2[Stop];
Stop--;
addbic(Bcnt,x);
addbic(Bcnt,y);
}
while (!(x==u && y==v || x==v && y==u));
}
}
else if (DFN[v]<LOW[u])
LOW[u]=DFN[v];
}
}
}
void solve()
{
bic(1,0);
if (start(S) && BFS())
printf("%d\n",Ans);
else
printf("NIE\n");
}
int main()
{
init();
solve();
return 0;
}
<h2><span class="mw-headline">倉庫管理員 </span></h2>
問題描述 碼頭倉庫是一塊N×M個格子的矩形，有的格子是空閒的——沒有任何東西，有的格子上已經堆放了沉重的貨物——太重了而不再可能被移動。 現在，倉庫管理員有一項任務，要將一個小箱子推到指定的格子上去。管理員可以在倉庫中移動，但不得跨過沉重的不可移動的貨物和箱子。當管理 員站在與箱子相鄰的格子上時，他可以做一次推動，把箱子推到另一個相鄰的格子。考慮到箱子很重，倉庫管理員爲了節省體力，想盡量減少推箱子的次數。你能幫 幫他麼？ 輸入文件 輸入文件第一行有兩個數N，M（1<=N,M<=100），表示倉庫是N×M的矩形。以下有N行，每行有M個字符，表示一個格子的狀態。
- S 表示該格子上放了不可移動的沉重貨物。
- w 表示該格子上沒有任何東西
- M 表示倉庫管理員初始的位置
- P 表示箱子的初始位置
K 表示箱子的目標位置
輸出文件 輸出文件只有一行，一個數，表示倉庫管理員最少要推多少次箱子。如果倉庫管理員不可能將箱子推到目標位置，那麼請輸出NIE，表示無解。 樣例輸入
10 12 SSSSSSSSSSSS SwwwwwwwSSSS SwSSSSwwSSSS SwSSSSwwSKSS SwSSSSwwSwSS SwwwwwPwwwww SSSSSSSwSwSw SSSSSSMwSwww SSSSSSSSSSSS SSSSSSSSSSSS
樣例輸出7