记录编号	116782	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-08-27 08:33:58	内存使用	0.27 MiB

#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream in("lphone.in");
ofstream out("lphone.out");
struct sss{
	int s;
	queue<int> h,z;
};
sss a[2];
bool pd1[101][101]={0},pd2[101][101]={0},qwq=false;
int zj1,zj2,zj3,zj4,m,n,i,l,k,p,y,qdh,qdz,zdh,zdz,zh1=1,zh0=0,zh,zui=0;
char aiky;
void init();
void vocaloid1();
void vocaloid2();
int main()
{
	init();
	vocaloid1();
	vocaloid2();
	out<<zui<<endl;
	in.close();
	out.close();
	return 0;
}
void init()
{
	in>>m>>n;
	for(i=1;i<=n;i++)
	for(y=1;y<=m;y++)
	{
		in>>aiky;
		if(aiky!='.')
		{
			if(aiky=='*')
			{
				pd1[i][y]=true;
				pd2[i][y]=true;
			}
			else
			{
				if(qwq==false){qdh=i;qdz=y;qwq=true;}
				else{zdh=i;zdz=y;qwq=false;}
			}
		}
	}
}
void vocaloid1()
{
	a[0].s=0;
	a[1].s=0;
	i=qdh+1;
	while(i<=n&&pd1[i][qdz]!=true)
	{
		a[0].h.push(i);
		a[0].z.push(qdz);
		pd2[i][qdz]=true;
		a[0].s++;
		i++;
	}
	i=qdh-1;
	while(i>=1&&pd1[i][qdz]!=true)
	{
		a[0].h.push(i);
		a[0].z.push(qdz);
		pd2[i][qdz]=true;
		a[0].s++;
		i--;
	}
	i=qdz+1;
	while(i<=m&&pd1[qdh][i]!=true)
	{
		a[0].h.push(qdh);
		a[0].z.push(i);
		pd2[qdh][i]=true;
		a[0].s++;
		i++;
	}
	i=qdz-1;
	while(i>=1&&pd1[qdh][i]!=true)
	{
		a[0].h.push(qdh);
		a[0].z.push(i);
		pd2[qdh][i]=true;
		a[0].s++;
		i--;
	}
}
void vocaloid2()
{
	while(1)
	{
		while(a[zh0].s!=0)
		{
			zj1=a[zh0].h.front();a[zh0].h.pop();
			zj2=a[zh0].z.front();a[zh0].z.pop();
			a[zh0].s--;
			if(zj1==zdh&&zj2==zdz)
			{
				qwq=true;
				break;
			}
			zj3=zj1+1;
			while(zj3<=n&&pd1[zj3][zj2]!=true)
			{
				if(pd2[zj3][zj2]==false)
				{
					a[zh1].h.push(zj3);
					a[zh1].z.push(zj2);
					pd2[zj3][zj2]=true;
					a[zh1].s++;
				}
				zj3++;
			}
			zj3=zj1-1;
			while(zj3>=1&&pd1[zj3][zj2]!=true)
			{
				if(pd2[zj3][zj2]==false)
				{
					a[zh1].h.push(zj3);
					a[zh1].z.push(zj2);
					pd2[zj3][zj2]=true;
					a[zh1].s++;
				}
				zj3--;
			}
			zj3=zj2+1;
			while(zj3<=m&&pd1[zj1][zj3]!=true)
			{
				if(pd2[zj1][zj3]==false)
				{
					a[zh1].h.push(zj1);
					a[zh1].z.push(zj3);
					pd2[zj1][zj3]=true;
					a[zh1].s++;
				}
				zj3++;
			}
			zj3=zj2-1;
			while(zj3>=1&&pd1[zj1][zj3]!=true)
			{
				if(pd2[zj1][zj3]==false)
				{
					a[zh1].h.push(zj1);
					a[zh1].z.push(zj3);
					pd2[zj1][zj3]=true;
					a[zh1].s++;
				}
				zj3--;
			}
		}
		if(qwq==true) break;
		zh=zh0;
		zh0=zh1;
		zh1=zh;
		zui++;
	}
}