小A与小B

题意：小A与小B被困在一个n*m的迷宫中，'.'为可通过，'#'为障碍不可通过，'C'为小A初始位置，'D'为小B初始位置。小A可以上下左右左上左下右上右下8个方向移动，而小B只能上下左右移动，不过小B能一秒移动二次，而小A只能一秒移动一次。求小A与小B最早什么时候相遇？不能相遇只输出NO.

思路：分别bfs小A和小B，求出分别到达每一个位置的最早时间，初始时间为inf（一个很大的数），一个位置的相遇时间为二个到达时间的最大值，求所有位置相遇的最小值。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 100000007

using namespace std;

int n, m;

char s[1005][1005];
int dc[1005][1005], dd[1005][1005], xc, yc, xd, yd, dx[9]= {1,-1,0,0,-1,-1,1,1}, dy[9]= {0,0,1,-1,1,-1,1,-1};
struct w
{
    int x, y;
} w, w1;

void bfsc()
{
    queue<struct w> q;
    w.x=xc;
    w.y=yc;
    q.push(w);
    fill(dc[0],dc[0]+1005*1005,inf);
    dc[w.x][w.y]=0;
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        for(int i=0; i<8; i++)
        {
            w1.x=w.x+dx[i];
            w1.y=w.y+dy[i];
            if(w1.x>=0&&w1.x<n&&w1.y>=0&&w1.y<m&&dc[w1.x][w1.y]==inf&&s[w1.x][w1.y]!='#')
            {
                dc[w1.x][w1.y]=dc[w.x][w.y]+1;
                q.push(w1);
            }
        }
    }
}

void bfsd()
{
    queue<struct w> q;
    w.x=xd;
    w.y=yd;
    q.push(w);
    fill(dd[0],dd[0]+1005*1005,2*inf);
    dd[w.x][w.y]=0;
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            w1.x=w.x+dx[i];
            w1.y=w.y+dy[i];
            if(w1.x>=0&&w1.x<n&&w1.y>=0&&w1.y<m&&dd[w1.x][w1.y]==2*inf&&s[w1.x][w1.y]!='#')
            {
                dd[w1.x][w1.y]=dd[w.x][w.y]+1;
                q.push(w1);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    getchar();
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            scanf("%c",&s[i][j]);
            if(s[i][j]=='C')
            {
                xc=i;
                yc=j;
            }
            if(s[i][j]=='D')
            {
                xd=i;
                yd=j;
            }
            if(j!=m-1)
                getchar();
        }
        if(i!=n-1)
        {
            getchar();
        }
    }
    bfsc();
    bfsd();
    int z=inf;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            z=min(z,max(dc[i][j],(dd[i][j]+1)/2));
        }
    }
    if(z!=inf)
        cout << "YES" << "\n" << z << endl;
    else
        cout << "NO" << endl;
    return 0;
}