NC23486 小A与小B

题目大意：
小A和小B被困在里迷宫里的不同位置，小A可以向周围8个方向每次移动一个位置，而小B则可以向周围四个方向每次移动两个位置，问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

输入描述:
第一行两个整数N，M分别表示迷宫的行和列。（1≤n,m≤1000）
接下来一个N*M 的矩阵
其中"C"表示小A的位置,"D"表示小B的的位置，
"＃"表示不可通过的障碍，"."则是可以正常通过的位置。字符用空格隔开。

输出描述:
如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
题目分析：
小A和小B每次可以移动的距离不一样是问题的关键，仔细思考，我们可以将小A每次走一步和两步都以相同的时间表示出来即可将问题解决。这题我的解法是双起点bfs，将小A和小B的起始位置都push进一个队列里面，在往周围走的时候以不同的vis标记来记录小A和小B走过的路径，当小A走到有小B路径标记的点，或者小B走到小A之前的路径时，两人即可最早在此相遇，输出此时花费的时间即可。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define  endl '\n'
#define all(s) s.begin(),s.end()
#define lowbit(x) (x&-x)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define pb push_back
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
char mp[1010][1010]; 
int vis[1010][1010];
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,-1,1,1,-1,1,-1,-1};
//int dir[4][2]={0,1,0,-1,1,0,-1,0};
struct node{
    int x,y,k,step;
};
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    } 
    queue<node>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='C') q.push(node{i,j,1,0}),vis[i][j]=1;
            if(mp[i][j]=='D') q.push(node{i,j,2,0}),vis[i][j]=2;
        }
    }
    while(!q.empty()){
        node on=q.front();
        q.pop();
        if(on.k==1){
            for(int i=0;i<8;i++){
                int dx=on.x+dir[i][0],dy=on.y+dir[i][1];
                if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy]==1||mp[dx][dy]=='#') continue;
                if(vis[dx][dy]==2){
                    cout<<"YES"<<endl<<on.step+1;
                    return 0;
                }else{
                    vis[dx][dy]=1;
                    q.push(node{dx,dy,1,on.step+1});
                }
            }
        }
        if(on.k==2){
            for(int i=0;i<4;i++){
                int dx=on.x+dir[i][0],dy=on.y+dir[i][1];
                if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy]==2||mp[dx][dy]=='#') continue;
                if(vis[dx][dy]==1){
                    cout<<"YES"<<endl<<on.step+1;
                    return 0;                    
                }else{
                    vis[dx][dy]=2;
                    q.push(node{dx,dy,2,on.step+1});
                }
                for(int j=0;j<4;j++){
                    int fx=dx+dir[j][0],fy=dy+dir[j][1];
                    if(fx<1||fx>n||fy<1||fy>m||vis[fx][fy]==2||mp[fx][fy]=='#') continue;
                    if(vis[fx][fy]==1){
                        cout<<"YES"<<endl<<on.step+1;
                        return 0; 
                    }else{
                        vis[fx][fy]=2;
                        q.push(node{fx,fy,2,on.step+1});
                    }
                }
            }
        }
    }
    cout<<"NO";
}