白鳥面会(BFS)

白鳥が会う
タイトルの説明
2頭の白鳥は1つの部分の湖面に氷が張った湖の中で生活し、湖面の形状は長方形で、R行C列の小さな四角に分割され、いくつかの四角に氷が結ばれている.このような四角は氷格と呼ばれ、残りの四角は水格と呼ばれている.冬が過ぎて、湖面の氷がだんだん溶け始め、毎日水に隣接する氷の格子が溶けて水の格子に変わります.2つの格子が隣接するとは、水平または垂直方向に共通のエッジがあり、対角をなす2つの格子が隣接していないことを意味し、下図はサンプルデータの進化過程を示す.
 
白鳥は水中で水平または垂直方向に泳ぐしかなく、何日後に2羽の白鳥が会えるかを判断するプログラムを書く.
【入力形式】
入力ファイルの最初の行には、1≦R,C≦1500の2つのスペースで区切られた整数RとCが含まれ、次のR行には、湖面の初期状態を表すC文字が含まれ、「・」は水格、「X」は氷格、「L」は白鳥を表す.
【出力形式】
出力ファイルには、1行に1つの整数が含まれています.2羽の白鳥が隣接する日まで待つ日数を示します.
【入力サンプル】
8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...
【出力サンプル】
2
Hint
30%データ1≤R《400.1≤C《300
100%そのうち1≦R,C≦1500
テーマを見ると広捜だと感じられますが、枝を切ったり最適化したりする必要があります.白鳥が歩くのに時間がかからない、つまり、2羽の白鳥が水域につながっていれば、すぐに相手に会うことができるので、出会う時間を制限するのは氷の融解程度です.最初は考えが偏っていて、2羽の白鳥から同時に探したいと思っていました...
正しい方法は氷の融解時間を前処理し、白鳥1羽を起点に広く捜索することであり、SPFAのような最適化もあり、チームに入る前にキューにいるかどうかを判断するが、私の方法は最適化を加えると答えが誤って更新されるので、カードは常に低空をかすめている.
注意:白鳥は同じ点で出会う必要はありません.隣接すればいいです.生命を大切にして、STLから离れます!!!メモリが限界を超えて少なくないので、ループキューが大きいほうがいいです.
コードは次のとおりです.

#include
#include
#include
#define maxn 1501
#define maxx 20695015
#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline))//        
using namespace std;
fastcall IL int read()
{   char c=getchar();int x=0,y=1;
	while(c'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
fastcall IL int m_max(int x,int y){return x>y?x:y;}
const int mod=20695013;//     ，    
int n,m,cnt=0,mp[maxn][maxn],tail,head,steps[maxn][maxn];
struct node{int x,y,step;}q[maxx],tt[3];
fastcall IL void bfs1()//        
{	while(head<=tail)
	{	node u=q[head];++head;
		if(u.x1&&mp[u.x-1][u.y]==-1) mp[u.x-1][u.y]=2,steps[u.x-1][u.y]=u.step+1,q[++tail]=(node){u.x-1,u.y,u.step+1};
		if(u.y>1&&mp[u.x][u.y-1]==-1) mp[u.x][u.y-1]=2,steps[u.x][u.y-1]=u.step+1,q[++tail]=(node){u.x,u.y-1,u.step+1};
		if(u.ytmp1)// SPFA     
		{	mp[u.x+1][u.y]=tmp1;
			q[tail]=(node){u.x+1,u.y,tmp1};++tail;
			if(tail==mod) tail=0;//if(!ok[u.x+1][u.y]) ok[u.x+1][u.y]=1,        ，        
		}
		if(u.x>1&&mp[u.x-1][u.y]>tmp2)
		{	mp[u.x-1][u.y]=tmp2;
			q[tail]=(node){u.x-1,u.y,tmp2};++tail;
			if(tail==mod) tail=0;//if(!ok[u.x-1][u.y]) ok[u.x-1][u.y]=1,
		}
		if(u.y>1&&mp[u.x][u.y-1]>tmp4)
		{	mp[u.x][u.y-1]=tmp4;
			q[tail]=(node){u.x,u.y-1,tmp4};++tail;
			if(tail==mod) tail=0;//if(!ok[u.x][u.y-1]) ok[u.x][u.y-1]=1,
		}
		if(u.ytmp3)
		{	mp[u.x][u.y+1]=tmp3;
			q[tail]=(node){u.x,u.y+1,tmp3};++tail;
			if(tail==mod) tail=0;//if(!ok[u.x][u.y+1]) ok[u.x][u.y+1]=1,
		}
	}
}
int main()
{  	//freopen("swan.in","r",stdin);
	//freopen("swan.out","w",stdout);
	head=1;tail=0;char c;
	n=read();m=read();
	for(int i=1;i<=n;++i)
	{	for(int j=1;j<=m;++j)
		{	c=getchar();while(c!='.'&&c!='L'&&c!='X') c=getchar();
			if(c=='.') mp[i][j]=2,q[++tail]=(node){i,j,0};
			else if(c=='L'){q[++tail]=(node){i,j,0};mp[i][j]=2;++cnt;if(cnt==1) steps[i][j]=0;tt[cnt]=(node){i,j,0};}
			else mp[i][j]=-1;
		}
	}
	bfs1();
	memset(mp,0x7f,sizeof(mp));
	bfs();
	printf("%d",mp[tt[2].x][tt[2].y]);
	return 0;
}