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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int H,W,map[110][110];  //-1表示障碍 0表示可走
struct T{
	int x,y,mirror;
}c;
queue<T>q;
void INPUT(void)
{
	int i,j;
	char ch;
	freopen("lphone.in","r",stdin);
	freopen("lphone.out","w",stdout);
	scanf("%d%d\n",&W,&H);
	for(i=0;i<=H+1;i++)	
		for(j=0;j<=W+1;j++)
			map[i][j]=-1;
	for(i=1;i<=H;i++)
	{	
		for(j=1;j<=W;j++)
		{	
			scanf("%c",&ch);
		    if(ch=='.')map[i][j]=0;
			else if(ch=='C')
			{
				c.x=i;
				c.y=j;
				c.mirror=-1;
				if(q.size()==0)q.push(c);
				else map[i][j]=0;
			}
			scanf("\n");
		}
	}
}
void BFS(void)
{
	int x,y;
	T t;
	while(!q.empty())
	{
		x=q.front().x;
		y=q.front().y;
		if(x==c.x&&y==c.y){printf("%d\n",q.front().mirror);return;}
		t.mirror=q.front().mirror+1;
		q.pop();
		for(t.x=x-1,t.y=y;map[t.x][t.y]>-1;t.x--)
		{
			if(map[t.x][t.y]==0||map[t.x][t.y]>t.mirror)
			{
				q.push(t);
			    map[t.x][t.y]=t.mirror;
			}
		}      //北
		for(t.x=x+1,t.y=y;map[t.x][t.y]>-1;t.x++)
		{
			if(map[t.x][t.y]==0||map[t.x][t.y]>t.mirror)
			{
				q.push(t);
			    map[t.x][t.y]=t.mirror;
			}
		}      //南
		for(t.x=x,t.y=y-1;map[t.x][t.y]>-1;t.y--)
		{
			if(map[t.x][t.y]==0||map[t.x][t.y]>t.mirror)
			{
				q.push(t);
			    map[t.x][t.y]=t.mirror;
			}
		}      //西
		for(t.x=x,t.y=y+1;map[t.x][t.y]>-1;t.y++)
		{
			if(map[t.x][t.y]==0||map[t.x][t.y]>t.mirror)
			{
				q.push(t);
			    map[t.x][t.y]=t.mirror;
			}
		}      //东
	}
}
int main()
{
	INPUT();
	BFS();
	return 0;
}