记录编号	112774	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-07-17 08:54:47	内存使用	0.31 MiB

#include<fstream>
#include<deque>
using namespace std;
class xy
{
public:
	int x,y;
};
int main()
{
	ifstream fi("lphone.in");
	ofstream fo("lphone.out");
	deque<xy>dl;
	int w,h,p=0,mp[102][102];
	xy n[2],k,g;
	char map[102][102];
	fi>>w>>h;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
		{
			fi>>map[i][j];
			mp[i][j]=214748364;
			if(map[i][j]=='C')
			{
				n[p].x=i;
				n[p].y=j;
				p++;
			}
		}
	mp[n[0].x][n[0].y]=0;
	dl.push_back(n[0]);
	while(!dl.empty())
	{
		k=dl.front();
		dl.pop_front();
		g.y=k.y;
		for(int i=k.x-1;(map[i][k.y]!='*')&&(i>=1);i--)
		{
			if(mp[i][k.y]>mp[k.x][k.y]+1)
			{
				mp[i][k.y]=mp[k.x][k.y]+1;
				g.x=i;
				dl.push_back(g);
			}
		}
		for(int i=k.x+1;(map[i][k.y]!='*')&&(i<=h);i++)
		{
			if(mp[i][k.y]>mp[k.x][k.y]+1)
			{
				mp[i][k.y]=mp[k.x][k.y]+1;
				g.x=i;
				dl.push_back(g);
			}
		}
		g.x=k.x;
		for(int i=k.y-1;(map[k.x][i]!='*')&&(i>=1);i--)
		{
			if(mp[k.x][i]>mp[k.x][k.y]+1)
			{
				mp[k.x][i]=mp[k.x][k.y]+1;
				g.y=i;
				dl.push_back(g);
			}
		}
		for(int i=k.y+1;(map[k.x][i]!='*')&&(i<=w);i++)
		{
			if(mp[k.x][i]>mp[k.x][k.y]+1)
			{
				mp[k.x][i]=mp[k.x][k.y]+1;
				g.y=i;
				dl.push_back(g);
			}
		}
	}
	fo<<mp[n[1].x][n[1].y]-1<<endl;
	return 0;
}