参考博客
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e3+7;
int n,m,sx1,sy1,sx2,sy2,f;
char ch[N][N];
struct L{
int x,y,t;
};
queue<L>q[2];
int vis[N][N][3];
int xx[]={1,-1,0,0,1,-1,1,-1};
int yy[]={0,0,1,-1,1,-1,-1,1};
int bfs(int x){
int zt=q[x].size();
while(zt--){
for(int i=0;i<8-x*4;++i){
int dx=q[x].front().x+xx[i];
int dy=q[x].front().y+yy[i];
int dt=q[x].front().t+f;
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy][x]&&ch[dx][dy]=='.'){
if(vis[dx][dy][1-x]) retur***is[dx][dy][x]=1;
q[x].push((L){dx,dy,dt});
}
}
q[x].pop();
}
return 0;
}
int solve(){
int z=0;
while(!q[0].empty()||!q[1].empty()){
f=1;
if(z=bfs(0)) return z;
if(z=bfs(1)) return z;
f=0;
if(z=bfs(1)) return z;
}
return 0;
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> ch[i][j];
if(ch[i][j]=='C') sx1=i,sy1=j;
if(ch[i][j]=='D') sx2=i,sy2=j;
}
}
vis[sx1][sy1][0]=1;vis[sx2][sy2][1]=1;
q[0].push( (L){sx1,sy1,0} );
q[1].push( (L){sx2,sy2,0} );
int ans=solve();
if(ans){
cout << "YES\n";
cout << ans;
}
else cout << "NO";
return 0;
}