记录编号	584246	评测结果	AAAAAAAAAA
题目名称	[USACO Jan09] 激光电话	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-04 15:47:29	内存使用	0.00 MiB

#include<iostream>
#include<queue>
#include<cstring> 
#include<cstdio>
using namespace std;
int n,m,a[110][110],x1=0,x2=0,y1=0,y2=0,f[110][110][5];//f记录从哪个方向到达(x,y)，1-上，2-下，3-左，4-右 
queue< pair<int ,int> > q;
int p(int x,int y)//判断点(x,y)能否到达 
{
    if(x<1||x>n||y<1||y>m||a[x][y]==1)
    {
        return 0;
    }
    return 1;
}
void bfs()
{
    q.push(make_pair(x1,y1));
    f[x1][y1][1]=0;
    f[x1][y1][2]=0;
    f[x1][y1][3]=0;
    f[x1][y1][4]=0;
    while(q.size())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if(p(x-1,y))//向上扩展 
        {
            int flag=0;
            if(f[x-1][y][1]>f[x][y][1])
            {
                f[x-1][y][1]=f[x][y][1];
                flag=1;
            }
            if(f[x-1][y][1]>f[x][y][3]+1)
            {
                f[x-1][y][1]=f[x][y][3]+1;
                flag=1;
            }
            if(f[x-1][y][1]>f[x][y][4]+1)
            {
                f[x-1][y][1]=f[x][y][4]+1;
                flag=1;
            }
            if(flag==1)
            {
                q.push(make_pair(x-1,y));
            }
        }
        if(p(x+1,y))//向下扩展 
        {
            int flag=0;
            if(f[x+1][y][2]>f[x][y][2])
            {
                f[x+1][y][2]=f[x][y][2];
                flag=1;
            }
            if(f[x+1][y][2]>f[x][y][3]+1)
            {
                f[x+1][y][2]=f[x][y][3]+1;
                flag=1;
            }
            if(f[x+1][y][2]>f[x][y][4]+1)
            {
                f[x+1][y][2]=f[x][y][4]+1;
                flag=1;
            }
            if(flag==1)
            {
                q.push(make_pair(x+1,y));
            }
        }
        if(p(x,y-1))//向左扩展 
        {
            int flag=0;
            if(f[x][y-1][3]>f[x][y][3])
            {
                f[x][y-1][3]=f[x][y][3];
                flag=1;
            }
            if(f[x][y-1][3]>f[x][y][1]+1)
            {
                f[x][y-1][3]=f[x][y][1]+1;
                flag=1;
            }
            if(f[x][y-1][3]>f[x][y][2]+1)
            {
                f[x][y-1][3]=f[x][y][2]+1;
                flag=1;
            }
            if(flag==1)
            {
                q.push(make_pair(x,y-1));
            }
        }
        if(p(x,y+1))//向右扩展 
        {
            int flag=0;
            if(f[x][y+1][4]>f[x][y][4])
            {
                f[x][y+1][4]=f[x][y][4];
                flag=1;
            }
            if(f[x][y+1][4]>f[x][y][1]+1)
            {
                f[x][y+1][4]=f[x][y][1]+1;
                flag=1;
            }
            if(f[x][y+1][4]>f[x][y][2]+1)
            {
                f[x][y+1][4]=f[x][y][2]+1;
                flag=1;
            }
            if(flag==1)
            {
                q.push(make_pair(x,y+1));
            }
        }
    }
}
int main()
{
    freopen("lphone.in","r",stdin);
    freopen("lphone.out","w",stdout);
    memset(a,0,sizeof(a));
    memset(f,0x3f,sizeof(f));
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char l;
            cin>>l;
            if(l=='*')
            {
                a[i][j]=1;
            }
            if(l=='C')
            {
                if(x1==0)
                {
                    x1=i;
                    y1=j;
                }
                else
                {
                    x2=i;
                    y2=j;
                }
            }
        } 
    }
    bfs();
    cout<<min(f[x2][y2][1],min(f[x2][y2][2],min(f[x2][y2][3],f[x2][y2][4])));//四个方向中选择一个最小的 
    return 0;
}