记录编号	131980	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	苜	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-10-25 07:48:21	内存使用	0.54 MiB

#include<cstdio>
#include<queue>
using namespace std;
const int INF=~0U>>2;
const int mx[4]={-1,0,0,1},
		  my[4]={0,-1,1,0};
struct node
{
	int x,y,dirc;
};
int a[101][101],f[101][101][4];
int cx[2],cy[2],cn=-1,n,m;
bool fg[101][101][4];
inline node made(int x,int y,int d)
{
	node nod;
	nod.x=x;nod.y=y;nod.dirc=d;
	return nod;
}
inline int P (int d1,int d2)
{
	if (d1==d2) return 0;
	if (d1+d2==3) return INF;
	return 1;
}
void bfs();
int main()
{
	freopen("lphone.in","r",stdin);
	freopen("lphone.out","w",stdout);
	scanf("%d%d",&n,&m);
	char ch;
	for (int i=1;i<=m;i++)
	for (int j=1;j<=n;j++)
	{
		for (int k=0;k<4;k++) f[i][j][k]=INF;
		scanf("%c",&ch);
		while (ch=='\n') scanf("%c",&ch);
		if (ch=='C') cx[++cn]=i,cy[cn]=j;
		if (ch!='*') a[i][j]=1;
	}
	bfs();
	int ans=INF;
	for (int k=0;k<4;k++)
	if (ans>f[cx[1]][cy[1]][k]) ans=f[cx[1]][cy[1]][k];
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void bfs()
{
	queue<node> q;
	for (int k=0;k<4;k++)
	{
		f[cx[0]][cy[0]][k]=0;
		int xx=cx[0]+mx[k],yy=cy[0]+my[k];
		if (xx>0&&xx<=m&&yy>0&&yy<=n&&a[xx][yy])
		{
            q.push(made(xx,yy,k));
            f[xx][yy][k]=0;
            fg[xx][yy][k]=true;
		}
	}
	while (!q.empty())
	{
		node nn=q.front();
		q.pop();
		fg[nn.x][nn.y][nn.dirc]=false;
        for (int k=0;k<4;k++)
		{
            int xx=nn.x+mx[k],yy=nn.y+my[k];
        	if (xx>0&&xx<=m&&yy>0&&yy<=n&&a[xx][yy])
        	{
				int p=P(nn.dirc,k);
				if (f[xx][yy][k]>f[nn.x][nn.y][nn.dirc]+p)
				{
                    f[xx][yy][k]=f[nn.x][nn.y][nn.dirc]+p;
                    if (!fg[xx][yy][k])
                    {
                        fg[xx][yy][k]=true;
                        q.push(made(xx,yy,k));
					}
				}
			}
		}
	}
}