POI 1999 仓库管理员 Store−keeper
This post is written in Chinese. Please consider using Google Translate
这道题描述的是我们玩过的经典的小游戏，推箱子。由于要求步数最少，基本的想法是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