小A与小B(bfs/枚举/双向)

两种bfs解法
解法一（315ms）：
关于这种解，我最后放了个33%的代码，有没有大佬指正一下错误
应该错在关于B的移动方式了。
思路

让A在图上跑一次bfs记录A到达每个点的最短时间
让B在图上跑一次bfs记录B到图上每个点的最短时间
然后枚举每个点让他们在这里相遇，取最小值

注意小B每次是跑两个点
代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=2e5+7;
const ll mod = 1e9+7;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,vis[1010][1212],x1,x2,y2,y11,step2[1211][1212],step1[1211][1212];
char s[1212][1212];
int dx[8]= {1,-1,0,0,1,-1,1,-1};
int dy[8]= {0,0,1,-1,1,1,-1,-1};
void bfs1() {
    queue<PII>q;
    q.push({x1,y11});
    vis[x1][y11]=1;
        step1[x1][y11]=0;
    while(q.size()) {
        PII fr=q.front();
        q.pop();
        ll x=fr.first;
        ll y=fr.second;
        for(int i=0 ; i<8 ; i++) {
            ll x3=x+dx[i];
            ll y3=y+dy[i];
            if(x3<=0||y3<=0||y3>m||x3>n||vis[x3][y3]||s[x3][y3]=='#') continue;
            vis[x3][y3]=1;
            step1[x3][y3]=step1[x][y]+1;
            q.push({x3,y3});
        }
    }
}
void bfs2() {
    queue<PII>q;
    q.push({x2,y2});
    vis[x2][y2]=1;
    step2[x2][y2]=0;
    while(q.size()) {
        PII fr=q.front();
        q.pop();
        ll x=fr.first;
        ll y=fr.second;
        for(int i=0 ; i<4 ; i++) {
            ll x3=x+dx[i];
            ll y3=y+dy[i];
            if(x3<=0||y3<=0||y3>m||x3>n||vis[x3][y3]||s[x3][y3]=='#') continue;
            vis[x3][y3]=1;
            step2[x3][y3]=step2[x][y]+1;
            q.push({x3,y3});
        /*  ll x4=x3+dx[i];
            ll y4=y3+dy[i];
            if(x4<=0||y4<=0||y4>m||x4>n||vis[x4][y4]||s[x4][y4]=='#') continue;
            vis[x4][y4]=1;
            step2[x4][y4]=step2[x][y]+1;
            q.push({x4,y4});*/
        }
    }
}
int UpMing() {
    n=read();
    m=read();
    mst(step1,-1);
    mst(step2,-1);
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++) {
            cin>>s[i][j];
            if(s[i][j]=='C') x1=i,y11=j;
            else if(s[i][j]=='D') x2=i,y2=j;
        }
    bfs1();
    mst(vis,0);
    bfs2();
    ll flag=0,ans=inf;
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++)
            if(step1[i][j]!=-1&&step2[i][j]!=-1) ans=min(ans,max(step1[i][j],(step2[i][j]+1)/2)),flag=1;
    if(flag)puts("YES") ,out(ans);
    else puts("NO");
    Accept;
}    

解法二（）

把A，B同时加入队列中每秒一起向四周行动一次
如果A走到了B走过的点或者B走到了A走过的点或者A，B同时走到了一个点
那么当前时间就是最短时间

代码

题解里都是

33%

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=2e5+7;
const ll mod = 1e9+7;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,vis[1010][1212],x1,x2,y2,y11,step2[1211][1212],step1[1211][1212];
char s[1212][1212];
int dx[8]= {1,-1,0,0,1,-1,1,-1};
int dy[8]= {0,0,1,-1,1,1,-1,-1};
void bfs1() {
    queue<PII>q;
    q.push({x1,y11});
    vis[x1][y11]=1;
    step1[x1][y11]=0;
    while(q.size()) {
        PII fr=q.front();
        q.pop();
        ll x=fr.first;
        ll y=fr.second;
        for(int i=0 ; i<8 ; i++) {
            ll x3=x+dx[i];
            ll y3=y+dy[i];
            if(x3<=0||y3<=0||y3>m||x3>n||vis[x3][y3]||s[x3][y3]=='#') continue;
            vis[x3][y3]=1;
            step1[x3][y3]=step1[x][y]+1;
            q.push({x3,y3});
        }
    }
}
void bfs2() {
    queue<PII>q;
    q.push({x2,y2});
    vis[x2][y2]=1;
    step2[x2][y2]=0;
    while(q.size()) {
        PII fr=q.front();
        q.pop();
        ll x=fr.first;
        ll y=fr.second;
        for(int i=0 ; i<4 ; i++) {
            ll x3=x+dx[i];
            ll y3=y+dy[i];
            if(x3<=0||y3<=0||y3>m||x3>n||s[x3][y3]=='#'||vis[x3][y3]) continue;
            vis[x3][y3]=1;
            step2[x3][y3]=step2[x][y]+1;
            q.push({x3,y3});
            ll x4=x3+dx[i];
            ll y4=y3+dy[i];
            if(x4<=0||y4<=0||y4>m||x4>n||vis[x4][y4]||s[x4][y4]=='#') continue;
            vis[x4][y4]=1;
            step2[x4][y4]=step2[x][y]+1;
            q.push({x4,y4});
        }
    }
}
int UpMing() {
    n=read();
    m=read();
    mst(step1,-1);
    mst(step2,-1);
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++) {
            cin>>s[i][j];
            if(s[i][j]=='C') x1=i,y11=j;
            else if(s[i][j]=='D') x2=i,y2=j;
        }
    bfs1();
    mst(vis,0);
    bfs2();
    ll flag=0,ans=inf;
    for(int i=1 ; i<=n ; i++)
        for(int j=1 ; j<=m ; j++)
            if(step1[i][j]!=-1&&step2[i][j]!=-1) ans=min(ans,max(step1[i][j],step2[i][j])),flag=1;
    if(flag)puts("YES") ,out(ans);
    else puts("NO");
    Accept;
}
/*

*/