记录编号	129673	评测结果	MMMM
题目名称	加法问题	最终得分	0
用户昵称	RP++	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2014-10-20 17:59:36	内存使用	0.00 MiB

#include<queue>
#include<cstdio>
using namespace std;
char ch[1501][1501];
int father[2250001],ans[1501][1501];
int a[5]={0,1,-1,0,0};
int b[5]={0,0,0,1,-1};
bool flag[1501][1501];
int h,l,h1,h2,r1,r2,s,t,x,y;;
queue<int>qa1,qa2,qb1,qb2,q1,q2;
inline int find(int x){
	if(x!=father[x])father[x]=find(father[x]);
	return father[x];
}
inline int my_max(int a,int b){
	if(a>b)return a;
	else return b;
}
int main(){
	freopen("aplusb.in","r",stdin);
	freopen("aplusb.out","w",stdout);
	scanf("%d%d",&h,&l);
	for(int i=1;i<=h;i++)	
		for(int j=1;j<=l;j++){
			ch[i][j]=getchar();
			if(ch[i][j]=='\n')ch[i][j]=getchar();
			if(ch[i][j]=='X')continue;
			if(ch[i][j]=='L'){
				if(!h1){
						qa1.push(i),qa2.push(j);
						h1=(i-1)*l+j;
				}
				else{
						qb1.push(i),qb2.push(j);
						h2=(i-1)*l+j;
				}
			}
			ch[i][j]='.';
			q1.push(i),q2.push(j);
		}
	for(int i=1;i<=h*l;i++)father[i]=i;
	while(!qa1.empty()){
		x=qa1.front();
		y=qa2.front();
		qa1.pop(),qa2.pop();
		r1=find((x-1)*l+y);
		for(int i=1;i<=4;i++){
			s=x+a[i],t=y+b[i];
			if(ch[s][t]=='.'&&!flag[s][t]){
				flag[s][t]=true;
				r2=find((s-1)*l+t);
				if(r1!=r2)father[r2]=r1;
				qa1.push(s),qa2.push(t);
			}
		}
	}
	while(!qb1.empty()){
		x=qb1.front();
		y=qb2.front();
		r1=find((x-1)*l+y);
		qb1.pop(),qb2.pop();
		for(int i=1;i<=4;i++){
			s=x+a[i],t=y+b[i];
			if((ch[s][t]=='.')&&(!flag[s][t])){
				flag[s][t]=true;
				r2=find((s-1)*l+t);
				if(r1!=r2)father[r2]=r1;
				qb1.push(s),qb2.push(t);
			}
		}
	}
	while(1){
		x=q1.front(),y=q2.front();
		q1.pop(),q2.pop();
		r1=find((x-1)*l+y);
		for(int i=1;i<=4;i++){
			s=x+a[i],t=y+b[i];
			if(s<=0||t<=0||s>h||t>l)continue;
			r2=find((s-1)*l+t);
			if(r1!=r2)father[r2]=r1;
			if(ch[s][t]=='X'){
				q1.push(s),q2.push(t);
				ans[s][t]=ans[x][y]+1;
				ch[s][t]='.';
			}
			else{
				if(find(h1)==find(h2)){
					printf("%d",my_max(ans[x][y],ans[s][t]));
					return 0;
				}
			}
		}
	}
}