- 小信小友逛庙会
题目ID：9774必做题100分
最新提交：
Wrong Answer
20 分
历史最高：
Wrong Answer
20 分
时间限制: 1000ms
空间限制: 262144kB
题目描述
小信与小友相约逛庙会。但是庙会人很多，他们走散了。
庙会能表示成 n×m 的矩阵，小信在’C’，小友在’D’，'.‘表示能走，’#'表示店铺（也就是不能走）。
每分钟，小信可以往8个方向移动一格，而小友可以移动一次或者两次，每次可以往4个方向（上下左右）移动一格，两次移动方向可以不同。
请问至少需要多少分钟，他们才能相遇。
输入格式：
第一行包含两个整数 n ,m，表示城市的地图大小。
接下来 n 行 m 列的地图。注意，连续两个字符中间有空格。
输出格式：
如果他们不能相遇，输出 NO，否则第一行输出 YES，第二行输出他们相遇所需要的最少时间。
WA代码：
#include<bits/stdc++.h>
using namespace std;
struct point{
int x,y;
}st1,st2;
int n,m,ans=INT_MAX;
char mp[1005][1005];
int s1[1005][1005],s2[1005][1005];
int dx[]={0,1,0,-1,1,-1,1,-1},dy[]={1,0,-1,0,1,1,-1,-1};
void bfsc(point st){
queue<point>que;
que.push(st);
memset(s1,-1,sizeof s1);
s1[st1.x][st1.y]=0;
while(que.size()){
point hd=que.front();
que.pop();
for(int i=0;i<8;i++){
int nx=hd.x+dx[i];
int ny=hd.y+dy[i];
if(nx<1||ny<1||nx>n||ny>m||s1[nx][ny]!=-1||mp[nx][ny]=='#')continue;
s1[nx][ny]=s1[hd.x][hd.y]+1;
que.push({nx,ny});
}
}
}
void bfsd(point st){
queue<point>que;
que.push(st);
memset(s2,-1,sizeof s2);
s2[st2.x][st2.y]=0;
while(que.size()){
point hd=que.front();
que.pop();
for(int i=0;i<4;i++){
int nx=hd.x+dx[i];
int ny=hd.y+dy[i];
if(nx<1||ny<1||nx>n||ny>m||s2[nx][ny]!=-1||mp[nx][ny]=='#')continue;
s2[nx][ny]=s2[hd.x][hd.y]+1;
que.push({nx,ny});
for(int j=0;j<4;j++){
int nnx=nx+dx[i];
int nny=ny+dy[i];
if(nnx<1||nny<1||nny>n||nny>m||s2[nnx][nny]!=-1||mp[nnx][nny]=='#')continue;
s2[nnx][nny]=s2[nx][ny]+1;
que.push({nnx,nny});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
if(mp[i][j]=='C')st1.x=i,st1.y=j;
if(mp[i][j]=='D')st2.x=i,st2.y=j;
}
}
bfsc(st1);
bfsd(st2);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i][j]!=-1&&s2[i][j]!=-1)
ans=min(ans,max(s1[i][j],s2[i][j]));
}
}
if(ans!=-1)cout<<"YES\n"<<ans;
else cout<<"NO";
}
大佬们，给个方案吧 