比赛 20130729 评测结果 AAAAAAAAAA
题目名称 激光电话 最终得分 100
用户昵称 努力吧 运行时间 0.004 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2014-07-17 10:58:17
显示代码纯文本
    #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;
    }