记录编号	9639	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[POI 1999] 仓库管理员(Store-Keeper)	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.133 s
提交时间	2009-04-08 09:06:00	内存使用	2.49 MiB

/* 
 * 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;
}