小A和小B（BFS）

题意：略。

题记：将小A和小B做为起点BFS两次，分别记录下小A和小B到每个位置的时间，最后枚举小A和小B相遇的位置，取小A和小B到当前位置的时间的最大值（相当于小A和小B在这个位置相遇）。

#include<bits/stdc++.h>

using namespace std;
const int N=1010,INF=0x3f3f3f3f;
int n,m,dx1,dx2,dy1,dy2;
int dis[][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,-1,-1,1};
//八个方向
char s[N][N];
bool vis[N][N];
int t1[N][N];
int t2[N][N];
struct Node{
    int x,y,step;
};

bool check(int x,int y){
    if(x<1||x>n||y<1||y>m||vis[x][y]||s[x][y]=='#')
        return false;
    return true;
}

void bfs1(){
    memset(vis,0,sizeof(vis));
    queue<Node>q;
    Node st,ne;
    st.x=dx1;st.y=dy1;st.step=0;
    vis[dx1][dy1]=1;
    t1[dx1][dy1]=0;
    q.push(st);
    while(!q.empty()){
        st=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            ne.x=st.x+dis[i][0];
            ne.y=st.y+dis[i][1];
            ne.step=st.step+1;
            if(check(ne.x,ne.y)){
                vis[ne.x][ne.y]=1;
                t1[ne.x][ne.y]=ne.step;
                q.push(ne);
            }
        }
    }
}

void bfs2(){
    memset(vis,0,sizeof(vis));
    queue<Node>q;
    Node st,ne,ed;
    st.x=dx2;st.y=dy2;st.step=0;
    vis[dx2][dy2]=1;
    t2[dx2][dy2]=0;
    q.push(st);
    while(!q.empty()){
        st=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            ne.x=st.x+dis[i][0];
            ne.y=st.y+dis[i][1];
            ne.step=st.step+1;
            if(check(ne.x,ne.y)){
                vis[ne.x][ne.y]=1;
                t2[ne.x][ne.y]=ne.step;
                q.push(ne);
            for(int j=0;j<4;j++){
                ed.x=ne.x+dis[j][0];
                ed.y=ne.y+dis[j][1];
                ed.step=st.step+1;
                if(check(ed.x,ed.y)){
                    vis[ed.x][ed.y]=1;
                    t2[ed.x][ed.y]=ed.step;
                    q.push(ed);
                }
            }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            if(s[i][j]=='C'){
                dx1=i;
                dy1=j;
            }
            if(s[i][j]=='D'){
                dx2=i;
                dy2=j;
            }
        }
    memset(t1,-1,sizeof(t1));
    memset(t2,-1,sizeof(t2));
    bfs1();
    bfs2();
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<t1[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<t2[i][j]<<' ';
        cout<<endl;
    }
    */
    int ans=INF;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(t1[i][j]!=-1&&t2[i][j]!=-1)
                ans=min(ans,max(t1[i][j],t2[i][j]));
    if(ans==INF)cout<<"NO"<<endl;
    else cout<<"YES"<<endl<<ans<<endl;
    return 0;
}