Description
推箱子. (n,mleqslant 100)
Sol
Tarjan+边双连通分量+BFS.
直接搜索的复杂度是 (n^6) 记录人的位置,箱子的位置和转移.
箱子的位置相当于一个障碍.
先灌水,把移动到箱子周围,每次的状态都是人在箱子旁边,这样复杂度就降为了 (4n^4) .
每次BFS分两步,改变方向和移动箱子.
如果箱子所在位置不是割点,那么往所有方向都联通.
否则想改变方向的话,两点必须是双连通才行.
这样复杂度就降低了...判断的时候可以预处理出来.
这样判断可以变成 (O(1)) .但是我没有这么写,直接暴力判断两点是否有相同的双连通分量.
Code
#include<cstdio>
#include<cstring>
#include<utility>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
#define debug(a) cout<<#a<<"="<<a<<" "
#define mpr make_pair
#define x first
#define y second
typedef pair< int,int > pr;
const int N = 105;
int n,m,dx,dy,sx,sy,tx,ty,ans;
int id[N][N],a[N][N],isg[N*N],to[N*N][4],v[N][N],vis[N*N*4];
int dfsn[N*N],low[N*N],cnt,bcnt;
pr stk[N*N];int top;
vector< int > bl[N*N];
char s[N];
int mvx[]={ -1,1,0,0 };
int mvy[]={ 0,0,-1,1 };
struct S{ int x,y,r,d; };
queue< S > q;
void Print(int a[N][N]){
cout<<"------------------------------"<<endl;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",a[i][j],"
"[j==m]);
}
void insert(int x,int b){
for(int i=0,lim=bl[x].size();i<lim;i++) if(bl[x][i] == b) return;
bl[x].push_back(b);
}
void Tarjan(int u,int fa){
low[u]=dfsn[u]=++cnt;
for(int i=0,xx,yy;i<4;i++) if(to[u][i] && to[u][i]!=fa){
if(!dfsn[to[u][i]]){
stk[++top]=mpr(u,to[u][i]);
Tarjan(to[u][i],u);
low[u]=min(low[u],low[to[u][i]]);
if(dfsn[u]<=low[to[u][i]]){
++bcnt,isg[u]=1;
do{
xx=stk[top].x,yy=stk[top--].y;
insert(xx,bcnt),insert(yy,bcnt);
}while(!((xx==u && yy==to[u][i]) || (xx==to[u][i] && yy==u)));
}
}else low[u]=min(low[u],dfsn[to[u][i]]);
}
}
int Move(int x,int y,int r1,int r2){
if(!a[x+mvx[r2]][y+mvy[r2]]) return 0;
int now=id[x+mvx[r1]][y+mvy[r1]],gt=id[x+mvx[r2]][y+mvy[r2]];
if(!isg[id[x][y]]) return 1;
else{
for(int i=0,j,limi=bl[now].size(),limj=bl[gt].size();i<limi;i++)
for(j=0;j<limj;j++) if(bl[now][i] == bl[gt][j]) return 1;
}return 0;
}
void Fill(int fx,int fy){
if(fx == sx && fy == sy) return;
v[fx][fy]=1;
for(int i=0;i<4;i++) if(a[fx+mvx[i]][fy+mvy[i]] && !v[fx+mvx[i]][fy+mvy[i]] && (fx+mvx[i]!=sx || fy+mvy[i]!=sy))
Fill(fx+mvx[i],fy+mvy[i]);
}
int BFS(){
Fill(dx,dy);
// Print(v);
for(int i=0;i<4;i++) if(a[sx+mvx[i]][sy+mvy[i]]){
// debug(sx+mvx[i]),debug(sy+mvy[i])<<endl;
if(v[sx+mvx[i]][sy+mvy[i]]) vis[id[sx][sy]<<2|i]=1,q.push((S){ sx,sy,i,0 });
}
for(S now;!q.empty();){
now=q.front(),q.pop();
// cout<<now.x<<" "<<now.y<<" "<<now.r<<" "<<now.d<<endl;
if(now.x == tx && now.y == ty) return ans=now.d,1;
for(int i=0;i<4;i++){
if(now.r!=i && Move(now.x,now.y,now.r,i) && !vis[id[now.x][now.y]<<2|i]){
vis[id[now.x][now.y]<<2|i]=1;
if(!vis[id[now.x+mvx[i^1]][now.y+mvy[i^1]]<<2|i] && a[now.x+mvx[i^1]][now.y+mvy[i^1]]){
vis[id[now.x+mvx[i^1]][now.y+mvy[i^1]]<<2|i]=1;
q.push((S){ now.x+mvx[i^1],now.y+mvy[i^1],i,now.d+1 });
}
}else if(now.r == i){
if(!vis[id[now.x+mvx[i^1]][now.y+mvy[i^1]]<<2|i] && a[now.x+mvx[i^1]][now.y+mvy[i^1]]){
vis[id[now.x+mvx[i^1]][now.y+mvy[i^1]]<<2|i]=1;
q.push((S){ now.x+mvx[i^1],now.y+mvy[i^1],i,now.d+1 });
}
}
}
}return 0;
}
int main(){
// freopen("in.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=m;j++){
id[i][j]=i*m+j;
if(s[j] == 'S') a[i][j]=0;
else a[i][j]=1;
if(s[j] == 'M') dx=i,dy=j;
if(s[j] == 'P') sx=i,sy=j;
if(s[j] == 'K') tx=i,ty=j;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
if(a[i-1][j]) to[id[i][j]][0]=id[i-1][j];
if(a[i][j-1]) to[id[i][j]][1]=id[i][j-1];
if(a[i+1][j]) to[id[i][j]][2]=id[i+1][j];
if(a[i][j+1]) to[id[i][j]][3]=id[i][j+1];
}
Tarjan(id[tx][ty],0);
// Print(a);
if(BFS()) printf("%d
",ans);
else puts("NO");
return 0;
}