记录编号	77652	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2013-11-02 11:31:01	内存使用	0.33 MiB

#include<cstring>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
using namespace std;
ifstream fi("lphone.in");
ofstream fo("lphone.out");
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int W,H,Ans=10000;
pair <int,int> cow1,cow2;
char graph[101][101];
bool boo[101][101];
class Three
{
public:
	pair <int,int> d;
	int step;
};
void bfs()
{
	queue <Three> q;
	q.push((Three){cow1,-1});
	boo[cow1.first][cow1.second]=1;
	int steps=-1;
	Three tmp;
	while(!boo[cow2.first][cow2.second])
	{
		steps++;
		while(q.front().step<steps)
		{
			tmp=q.front();
			q.pop();
			for(int i=0;i<4;i++)
			{
				int tx=tmp.d.first+dx[i],ty=tmp.d.second+dy[i];
				for(;(tx>=1)&&(ty>=1)&&(tx<=H)&&(ty<=W)&&(graph[tx][ty]=='.');tx+=dx[i],ty+=dy[i])
				{
					if(boo[tx][ty])continue;
					boo[tx][ty]=1,q.push((Three){make_pair(tx,ty),steps});
				}
			}
		}
	}
	fo<<steps<<endl;
}
int main()
{
	fi>>W>>H;
	bool flag=false;
	for(int i=1;i<=H;i++)
		for(int j=1;j<=W;j++)
		{
			fi>>graph[i][j];
			if(graph[i][j]=='C')
			{
				if(!flag)
					cow1=make_pair(i,j),flag=1;
				else
					cow2=make_pair(i,j);
				graph[i][j]='.';
			}
			if(graph[i][j]=='*')
				boo[i][j]=1;
			else
				boo[i][j]=0;
		}
	bfs();
	return 0;
}