显示代码纯文本
/*
* Problem: POI1999 mag
* Author: Guo Jiabao
* Time: 2009.4.7 20:54
* State: Unsolved
* 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();
// printf("(%d,%d)\n",Map[i.x][i.y],i.p);
//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;
}
BYVoid